Комбинаторные алгоритмы

Question

[Aler]

Посоветуйте статью по сабжу c реализацией для n-предметов в m-ячеек (желательно на python)

P.S. Хочу сделать список колор-кодов для пререндера набора текстур для кубиков, то есть код где 1 — красный, 2 — желтый и 3-зеленый, а финальный код выглядит примерно так: «122311».

P.S.S. Правильно ли я посчитал? Что если 6 ячеек (6 граней) и 3 цвета, то в финале 216 комбинаций (6^3)

Answer 1

[Ano]

Вложенные циклы, конечно, эквивалентны, но на python идеологически правильным будет

import itertools

itertools.product( ('1', '2', '3'), repeat=6)


Answer 2

[Григорий]

Относительно PPS. Посчитали вы не правильно. Количество таких комбинаций 3^6 = 729 — троичная система счисления с шестью позициями.

Если говорить только про кубики, то не 729, а меньше, потому как одни комбинации могут получаться из других путем простого поворота.

Comments

[Aler]

Я совсем плохой. Может знаете способ узнать одинаковые комбинации при повороте?

Answer 3

[Вячеслав Плиско]

неправильно. нужно систему исчислении (3 цвета) возводить в степень разрядности (6 ячеек). запомнить легко, если сравнивать со знакомой десятичной системой. система 10 разрядов 3, соответственно вариантов 1000.

в вашем варианте можно тупо сделать три цикла и не «заморачиваться» алгоритмом перестановок.

Answer 4

[lecter]

www.kolasc.net.ru/cdo/books/tv/page13.html

Comments

[lecter]

Случайно нажал ctrl + Enter. Если не учитывать возможность поворота, как написали выше, то в вашем случае используется формула размещения.

Answer 5

[lecter]

www.kolasc.net.ru/cdo/books/tv/page13.html

Answer 6

[Владимир Мартьянов]

Если нужен полный перебор — тут хороший алгоритм описан www.wasm.ru/article.php?article=cycle_pwd