VPF::Алгоритм генерации уникальных комбинаций

o.s.a.

Дата 2.10.2008, 19:29 (ссылка)

(нет голосов)

Загрузка ...

Xo4y B MocKBy

Профиль
Группа: Участник
Сообщений: 312
Регистрация: 16.2.2005
Где: Ташкент

Репутация: нет
Всего: 15

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

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

--------------------

Не могу стоять, пока другие работают, пойду полежу.

Sunvas

Дата 2.10.2008, 19:36 (ссылка)

(нет голосов)

Загрузка ...

Соль и сахар

Профиль
Группа: Участник
Сообщений: 3388
Регистрация: 12.3.2006
Где: Тосно

Репутация: нет
Всего: 89

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

--------------------

Воспитывая детей по своему образу и подобию, родители почему-то надеются, что они будут лучше их.

teroni

Дата 2.10.2008, 23:54 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 381
Регистрация: 15.5.2007
Где: Днепропетровск

Репутация: 1
Всего: 22

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

Код


$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);

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

Это сообщение отредактировал(а) teroni - 2.10.2008, 23:59

o.s.a.

Дата 3.10.2008, 07:24 (ссылка)

(нет голосов)

Загрузка ...

Xo4y B MocKBy

Профиль
Группа: Участник
Сообщений: 312
Регистрация: 16.2.2005
Где: Ташкент

Репутация: нет
Всего: 15

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

--------------------

Не могу стоять, пока другие работают, пойду полежу.

Glip

Дата 4.10.2008, 11:29 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 473
Регистрация: 30.12.2006

Репутация: нет
Всего: 18

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

--------------------

gibbzy

Дата 9.10.2008, 18:58 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 97
Регистрация: 25.1.2008

Репутация: нет
Всего: 3

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

тоесть

Код


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

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

1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| PHP: Для профи \| Следующая тема »

Внимание: данный раздел предназначен для решения сложных, нестандартных задач.