Модераторы: skyboy, MoLeX, Aliance, ksnk
  

Поиск:

Ответ в темуСоздание новой темы Создание опроса
> Алгоритм генерации уникальных комбинаций, длины N из алфавиту M 
:(
    Опции темы
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'.


--------------------
Не могу стоять, пока другие работают, пойду полежу.
PM MAIL ICQ   Вверх
Sunvas
Дата 2.10.2008, 19:36 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Соль и сахар
****


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

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



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


--------------------
Воспитывая детей по своему образу и подобию, родители почему-то надеются, что они будут лучше их.
PM MAIL   Вверх
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
PM MAIL   Вверх
o.s.a.
Дата 3.10.2008, 07:24 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Xo4y B MocKBy
**


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

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



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



--------------------
Не могу стоять, пока другие работают, пойду полежу.
PM MAIL ICQ   Вверх
Glip
Дата 4.10.2008, 11:29 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


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

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



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


--------------------
user posted image
PM MAIL   Вверх
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
но я не уверен что это самый рациональный способ
PM MAIL WWW ICQ   Вверх
  
Ответ в темуСоздание новой темы Создание опроса

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

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


 




[ Время генерации скрипта: 0.0762 ]   [ Использовано запросов: 21 ]   [ GZIP включён ]


Реклама на сайте     Информационное спонсорство

 
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности     Powered by Invision Power Board(R) 1.3 © 2003  IPS, Inc.