Как найти все комбинации символов?

Question

[Rrooom]

Есть массив символов - ['a', 'b', 'c'].

Нужно составить из них перестановки (?), что бы получить все варианты матриц 3х3 из этих символов:

[ ['a', 'a', 'a'], ['a', 'a', 'a'], ['a', 'a', 'a']], 
[['a', 'a', 'a'], ['a', 'a', 'a'], ['a', 'a', 'b']],
[['a', 'a', 'a'], ['a', 'a', 'a'], ['a', 'b', 'b']], 
...,
 [ ['a', 'b', 'c'], ['a', 'b', 'c'], ['a', 'b', 'c']], 
...,
 [ ['c', 'c', 'c'], ['c', 'c', 'c'], ['c', 'c', 'c']]

Можете рассказать алгоритм, как это сделать? А так же тыкнуть носом в теорию?

UPD.
Я нашел, что мне было нужно в стандартной библиотеке питона:

print list(itertools.product(['a', 'b', 'c'], repeat=9))

Но печальность ситуации, что я не понимаю, как такое можно реализовать вручную. Недостаток знаний..

Answer 1

[Mrrl]

Такие матрицы, судя по всему, описывают возможные бинарные операции на множестве {'a','b','c'}, т.е. функции от двух переменных из этого множества, принимающие значения в этом же множестве.
Всего таких функций будет 3^9=19683. Поэтому достаточно перебрать числа от 0 до 3^9-1, и троичную запись каждого из них превратить в матрицу. На C# это бы выглядело так:

char[,] matr=new char[3,3];
    for(int i=0;i<19683;i++){
        int a=i;
        for(int j=9;--j>=0;){
            matr[j/3,j%3]=(char)('a'+a%3);
            a/=3;
        }
        Process(matr);
    }

Comments

[Андрей]

Тогда непонятно слово "перестановка" в условии задачи. То, что описываете Вы, это не перестановка, а выборка с повторениями.

[Mrrl]

Мне тоже непонятно. Если бы было 9 символов, можно было бы понять (9! матриц). Матрица, в которой каждая строчка - перестановка, но строчки друг с другом не связаны - странная постановка. Латинские квадраты 3*3? Их совсем немного. Какие-нибудь таблицы Кэлли? Тоже маловато будет. А пример, приведённый в вопросе, является как раз выборкой с повторениями.

[Rrooom]

@Mrrl Спасибо, очень похоже на то что нужно. Но.
char[,] - что здесь значит запятая?
('a'+a%3) - что мы делаем здесь?
Process - под этим что подразумевается?

И еще. Из какой дициплины вам стали известны непонятные слова "перестановка", "таблицы Кэлли", "выборкой с повторениями"?

[Mrrl]

Это из C#. Какие аналоги на Python, я не знаю.
1) char[,] - двумерный массив с индексами от 0 до 2 по каждой координате. Тип массива - символ.
2) (char)('a'+a%3) - прибавляем к коду символа 'a' остаток от деления a на 3. Если a%3==0, то получим тот же символ 'a', если a%3==1, то 'b', а если a%3==2, то 'c'.
3) функция, которая делает с матрицей то, что вам надо. Например, печатает.

"перестановка" и "таблица Келли" - термины из высшей алгебры, более конкретно - из теории групп (конечных).
Про "выборку с повторением" затрудняюсь ответить. Судя по всему, это комбинаторика, но насколько устоявшиеся в этой науке термины соответствуют современному языку программистов, я не разбирался.

Answer 2

[Форзенэлс Вотэва]

Извините, я пьян.
I am C'man in Python world.

#!/usr/bin/python                                                                                                                                              
                                                                                                                                                               
s = ['a','a','a','a','a','a','a','a','a']                                                                                                                      
print s                                                                                                                                                        
                                                                                                                                                               
def plus(s):                                                                                                                                                   
    i = -1                                                                                                                                                     
    cf = 1                                                                                                                                                     
    while cf == 1:                                                                                                                                             
        if (s[i] == 'a'):                                                                                                                                      
            cf = 0                                                                                                                                             
            s[i] = 'b'                                                                                                                                         
        elif s[i] == 'b':                                                                                                                                      
            cf = 0                                                                                                                                             
            s[i] = 'c'                                                                                                                                         
        elif (s[i] == 'c'):                                                                                                                                    
            cf = 1                                                                                                                                             
            s[i] = 'a'                                                                                                                                         
                                                                                                                                                               
        i -= 1                                                                                                                                                 
                                                                                                                                                               
while s != ['c','c','c','c','c','c','c','c','c']:                                                                                                              
    plus(s)                                                                                                                                                    
    print s

Comments

[Mrrl]

Вероятно, там должно быть не i=-1, а i=8?

[Форзенэлс Вотэва]

@Mrrl инвариантно

[Rrooom]

@captain_fistashka ответ. Но что вы здесь делали?!

[Форзенэлс Вотэва]

@Rrooom ниже коллега Mrrl описал суть. Правда мой пример без матриц, просто с линейным массивом, но суть от этого не меняется - сможете разбить на строки/столбцы. Это все возможные строки из 9 символов на множестве (алфавите) [ 'a', 'b', 'c' ].

Answer 3

[Андрей]

Я бы из такого задания решил, что сначала интересуют все перестановки внутри этой строки (выборка без возвращения) - их будет 6.
А потом из получившихся 6 строк составить все возможные варианты квадратных матриц (выборка с возвращением) - соответственно их будет 6^3=216.

Лексикографическая первая квадратная матрица будет [abc, abc, abc], потом [abc, abc, acb], [abc, abc, bac], ..., а заканчиваться это будет [cba, cba, cab], [cba, cba, cba].

Answer 4

[Илья Лесных]

Реализация примерно похожего алгоритма на PHP: Как лучше сделать код для перевода?