Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > PHP: Для профи > Алгоритм генерации уникальных комбинаций

Автор: o.s.a. 2.10.2008, 19:29

Почитал раздел алгоритмы, но там все примеры на паскале, кототый я плохо понимаю.
Поэтому хочется увидеть реализацию на php.

Задача.
Составить все возможные уникальные комбинации длиной N символов из алфавита, состояцего из M символов.
Уникальность заключается в том, что порядок роли не играет.
Т.е. если уже получена комбинация (для примера N=3) 'abc', то нужно исключить 'acb', 'bac'. 'bca'. 'cab'. 'cba'.

Автор: Sunvas 2.10.2008, 19:36

Когда-то писал. Правда на Delphi.. Но, думаю, поможет: http://forum.vingrad.ru/index.php?showtopic=113874&view=findpost&p=883003

Автор: teroni 2.10.2008, 23:54

Обычная рекурсия...

Код


$letters = 'abcdefgh';
$word_lenght = 4;
function print_word_recursive($word, $letter_number)
{
   global $letters, $word_lenght;
   if (strlen($word) == $word_lenght)
      {
      echo $word .'<br />';
      return 0;
      }
   for ($i = $letter_number; $i < strlen($letters); $i++)
      {
      print_word_recursive($word.$letters[$i], $i+1);
      }
   return 0;
}
print_word_recursive('', 0);

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

Автор: o.s.a. 3.10.2008, 07:24

teroni, как все оказывается гениально и просто, и как как раз, то что мне нужно (буквы в слове не должны повторяться).
Причем, пока сам на бумажке для $letters = 'abcd'; и $word_lenght = 2; всю работу функции не прогнал, ниче не понял smile

Автор: Glip 4.10.2008, 11:29

o.s.a., могу посоветовать в качестве разминки: вот у вас есть готовая реализация вашего функционала. попробуйте заменить рекурсию итерацией. то что сейчас global уйдет в аргументы функции

Автор: gibbzy 9.10.2008, 18:58

string = это массив букв

тоесть

Код


$hw = "hello_world";
echo $hw[0] \\  выдаст букву h

перемешать элементы массива не оч уж и сложно
есть куча алгоритмов рекурсивный думаю замечатльно подойдёт
http://algolist.manual.ru/maths/combinat/sequential.php
но я не уверен что это самый рациональный способ