Dolgofor Сообщение 16/08/2011 15:01 Копия темы
Работа – алгоритм перемешивания букв (комбинаторика). Вот мой алгоритм для вывода всех возможных комбинаций введённых букв (ActionScript 3.0):

            // перебираем массив букв
            private static function perebor (slovoArr:Array):Array
            {
                var pereborSpeed:Array = [ ]; // частота смены каждой буквы
                var countArr:Array = [ ]; // массив со счётчиками каждой буквы
                var resultArr:Array = [ ]; // массив с одним результирующим словом
                var resultsArr:Array = [ ]; // массив со всеми результирующими словами
 
                // заполняем массивы
                for (var i:uint = 0; i < slovoArr.length; i++)
                {
                    pereborSpeed.push(factorial(slovoArr.length – i – 1));
                    resultArr.push(i+1);
                    countArr.push(0);
                }

                // перебор слов
                for (var i2:uint = 0; i2 < factorial(slovoArr.length); i2++)
                {                
                    // перебор букв в этом слове
                    for (var i3:uint = 0; i3 < slovoArr.length; i3++)
                    {                    
                        // если счётчик этой буквы не истёк
                        if (countArr[i3] < pereborSpeed[i3])
                        {
                            countArr[i3] ++ // инкрементируем его
                        }
                        else // иначе
                        {
                            countArr[i3] = 1; // сбрасываем его

                            // обнуляем одно следующее значение, если это не последнее
                            if (i3 != (slovoArr.length-1))
                            {
                                resultArr[(i3+1)] = 0;
                            }

                            // инкрементируем букву в результате
                            resultArr = incrementResult(i3, resultArr);
                        }
                    }

                    // создаём слово-результат
                    var word:String = "";

                    for (var i6:uint = 0; i6 < resultArr.length; i6++)
                    {
                        word += slovoArr[resultArr[i6]-1];
                    }

                    // добавляем его в массив
                    resultsArr.push(word);
                }

                return resultsArr;
            }

            // меняем одну букву
            private static function incrementResult (i3:uint, resultArr:Array):Array
            {    
                var returned:Array; // возвращаемое значение
                var ok:Boolean = true; // true значит, что такой буквы нет

                resultArr[i3] ++

                // проверяем нет ли такой буквы в ранее использующихся символах
                for (var i5:uint = 0; i5 < i3; i5++)
                {
                    if (resultArr[i5] == resultArr[i3])
                    {        
                        ok = false;
                    }
                    else
                    {
                    }
                }

                if (ok == false)
                {
                    returned = incrementResult(i3, resultArr);
                }
                else
                {
                    returned = resultArr;
                }

                return returned
            }

            // функция вычисления факториала
            private static function factorial (a:uint):uint
            {
                var tempNew:uint;

                if (a == 0)
                {
                    tempNew = 1;
                }
                else
                {
                    tempNew = a;
                }

                for (var h:uint = 1; h < a; h++)
                {
                    tempNew *= h;
                }

                return tempNew;
            }

Результат работы программы на примере тестового слова NERD:

NERD, NEDR, NRED, NRDE, NDER, NDRE, ENRD, ENDR, ERND, ERDN, EDNR, EDRN, RNED, RNDE, REND, REDN, RDNE, RDEN, DNER, DNRE, DENR, DERN, DRNE, DREN.

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

Примеры:

FOO, FOO, OFO, OOF, OFO, OOF.

DOOR, DORO, DOOR, DORO, DROO, DROO, ODOR, ODRO, OODR, OORD, ORDO, OROD, ODOR, ODRO, OODR, OORD, ORDO, OROD, RDOO, RDOO, RODO, ROOD, RODO, ROOD.

Искать одинаковые слова в массиве с результатами и удалять по одному совпадению – не решение. Решение должно заключаться в изменении самого алгоритма перебора.

P.S. Все предложения и замечания по работе приветствуются в комментариях!