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

Есть массив символов - ['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))

Но печальность ситуации, что я не понимаю, как такое можно реализовать вручную. Недостаток знаний..
  • Вопрос задан
  • 8857 просмотров
Решения вопроса 2
Mrrl
@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);
    }
Ответ написан
Извините, я пьян.
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
Ответ написан
Пригласить эксперта
Ответы на вопрос 2
Я бы из такого задания решил, что сначала интересуют все перестановки внутри этой строки (выборка без возвращения) - их будет 6.
А потом из получившихся 6 строк составить все возможные варианты квадратных матриц (выборка с возвращением) - соответственно их будет 6^3=216.

Лексикографическая первая квадратная матрица будет [abc, abc, abc], потом [abc, abc, acb], [abc, abc, bac], ..., а заканчиваться это будет [cba, cba, cab], [cba, cba, cba].
Ответ написан
Комментировать
Реализация примерно похожего алгоритма на PHP: Как лучше сделать код для перевода?
Ответ написан
Комментировать
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы