Составление слова из букв заданного слова

[dima_s_d_s]

Допустим есть слово миранда, есть источник слов (допустим текстовый файл), нужно составить слова из букв заданного слова (мир, марина, рама ....).

Подскажите оптимальный вариант алгоритма.
Заранее благодарен.

[esperanto]

Оптимальный по какому критерию?

[andrew.virus]

Цитата dima_s_d_s @ 15.01.10, 16:01

Допустим есть слово миранда, есть источник слов (допустим текстовый файл), нужно составить слова из букв заданного слова (мир, марина, рама ....).

возмоден такой вариант:

1. генерируем все подмножества данного множества, учитывая ограничения на длину слова (см. эдесь)
2. для каждого слова строим перестановки без повторений (см. здесь)
3. сверяем найденные слова со словарем и получаем все слова, которые есть в словаре

[vk]

Словарь из файла организовать в виде дерева, в котором каждый путь - слово, а каждая вершина - буква.
Обходить дерево слева направо, осуществляя поиск очередной буквы-вершины в исходном слове. Если буква есть - вычеркнуть её из копии исходного слова и спускаться дальше по ветке, если нет - возврат.

[dima_s_d_s]

Цитата andrew.virus @ 15.01.10, 17:32

возмоден такой вариант:

1. генерируем все подмножества данного множества, учитывая ограничения на длину слова (см. эдесь)
2. для каждого слова строим перестановки без повторений (см. здесь)
3. сверяем найденные слова со словарем и получаем все слова, которые есть в словаре

Начну с первого.
1. генерируем все подмножества данного множества, учитывая ограничения на длину слова (см. эдесь)
Из статьи не совсем понял алгоритм, поискал по форуму примеры, в и тоге получил что-то похожее на следующее

$a = "миранда";
$count = 0;
for($i=0; $i<7; $i++){
    $cnt = 0;
    for($j=0; $j <= $count; $j++){
        $cnt++;
        $array[$count+$cnt] = $array[$j].$a[$i];
    }
    $count+=$cnt+1;
    $array[$count] = $a[$i];
}

Помогите привести до ума.

[dima_s_d_s]

Есть алгоритм Размещение
Там же есть пример организации алгоритма на Java.

import java.util.Arrays;
 
public class PermutationsWithRepetition {
    private Object[] source;
    private int variationLength;
 
    public PermutationsWithRepetition(Object[] source, int variationLength) {
        this.source = source;
        this.variationLength = variationLength;
    }
 
    public Object[][] getVariations() {
        int srcLength = source.length;
        int permutations = (int) Math.pow(srcLength, variationLength);
 
        Object[][] table = new Object[permutations][variationLength];
 
        for (int i = 0; i < variationLength; i++) {
            int t2 = (int) Math.pow(srcLength, i);
            for (int p1 = 0; p1 < permutations;) {
                for (int al = 0; al < srcLength; al++) {
                    for (int p2 = 0; p2 < t2; p2++) {
                        table[p1][i] = source[al];
                        p1++;
                    }
                }
            }
        }
 
        return table;
    }
 
    public static void main(String[] args) {
        PermutationsWithRepetition gen = new PermutationsWithRepetition(
                new Integer[]{1, 2, 3, 4, 5, 6, 7, 8, 9, 0},
                5);
 
        Object[][] variations = gen.getVariations();
 
        for (Object[] s : variations) {
            System.out.println(Arrays.toString(s));
        }
    }
}

Пример хороший, но он реализует размещение с повторениями.
Может есть подобный пример алгоритма, для размещение без повторений?

[andrew.virus]

dima_s_d_s набросал пример, который работает ...

function generateAllWords(baseStr: string; baseFile: string): TStrings;
// генерация слов на базе основного с проверкой по словарю
var
  indArr: array of byte;
  i, j, lenArr: integer;
  tmpStr: string;
  dicArr: TStrings;
 
begin
  lenArr:=length(baseStr);
  setlength(indArr, lenArr + 1);  // формирование массива индексов ...
                                        // ... для формирования базовых основ
  result:=TStringList.Create;
  // формирование списка основ для генерации слов ...
  // ... и получение на их основе полного списка
  // начальная инициализация массива индексов
  for i:=0 to lenArr do
    indArr[i]:=0;
  //
  while indArr[lenArr] <> 1 do
    begin
      i:=0; // индекс бита двоичного числа
      while indArr[i] = 1 do
        begin
          indArr[i]:=0; // моделируем перенос в следующий разряд, ...
                        // ... возникающий при сложении
          i:=i+1
        end;
      indArr[i]:=1;
      // получение простой подстроки от основы ...
      // ... для генерации слов
      tmpStr:='';
      for i:=0 to (lenArr - 1) do
        if indArr[i] = 1 then
          tmpStr:=tmpStr + baseStr[i + 1];
      // добавление очередной подстроки в список основ
      if length(tmpStr) > 1 then
        if result.IndexOf(tmpStr) < 0 then
          result.Add(tmpStr)
    end;
  // формирование списка реальных слов на ...
  // ... основе проверки по словарю
  dicArr:=TStringList.Create;
  dicArr.LoadFromFile(baseFile);
  for i:=(result.Count - 1) downto 0 do
    begin
      j:=dicArr.IndexOf(result[i]);
      if j < 0 then
        result.Delete(i)
    end;
  result.SaveToFile('out.txt')
end;

вызывается всё таким образом:

generateAllWords(edit1.text, 'in.txt');

для входного слова "маскарад" и словаря:

ар
ор
мортира
антивирус
маска
маскарад
дар
пена
ад
мор
парад
пенопласт
лиман
боль
лемон
фунт
кадр
дама
тиф
смерть

получаем:

маска
ар
ад
маскарад

з.ы.: в прилагаемом архиве пример целиком ...
Прикреплённый файлcombin_words.zip (2.89 Кбайт, скачиваний: 346)

[dima_s_d_s]

Цитата andrew.virus @ 16.01.10, 20:27

dima_s_d_s набросал пример, который работает ...
...
з.ы.: в прилагаемом архиве пример целиком ...

Большое спасибо.
Буду разбираться, жаль что не С/С++ или PHP

Сообщение отредактировано: dima_s_d_s - 17.01.10, 11:48