1

Пишу на Delphi. Нужна небольшая помощь с алгоритмом, или примером кода.

Есть набор символов (для примера 5 шт, но на самом деле будет больше сотни), a,b,с,d,e. Нужно составить список всех возможных комбинаций из этих символов. Например:

  1. a
  2. b
  3. c
  4. d
  5. e
  6. ab
  7. ac
  8. ad
  9. ...
  10. abcde
  11. ....

Но с условием, что каждый символ должен повторяться в комбинации, только один раз. И наборы символов "ab" и "ba" считать разными комбинациями.

-----ДОПОЛНЕНО-----

procedure Generate(list, comb: TStringList; idx: integer);
var
  temp :  TStringList;
  i, k : integer;
begin
  temp              := TStringList.Create;
  temp.Duplicates   := dupIgnore;
  temp.Sorted       := false;


  if idx >  list.Count-1 then begin
    if  comb.Count-1 > 0 then
      Form1.Memo1.Lines.Add(comb.Text);
    Exit;
  end;

  for k := 0 to comb.Count-1 do begin
    temp.Assign(comb);      // заменил строку присвоения на Assign
    temp.Insert(k, list[idx]);
    Generate(list, temp, idx + 1);
  end;
  Generate(list, comb, idx + 1);

comb.Free;
end;
13
  • 1
    Во-первых, где свои наработки? Во-вторых, для больше сотни вывод не получится, т.к. количество будет непомерное - например, для 20 символов - 6613313319248080000 вариантов.
    – MBo
    1 мая 2019 в 4:20
  • @MBo , большое спасибо за ответ! Изначально я поделил задачу на 2 части. 1) Поиск всех возможных вариантов 2) их фильтрация (т.к нужны будут не все) Но после Ваших слов, думаю будет правильнее фильтровать их на этапе создания комбинаций, и оставлять только нужные. Простой пример как я себе это представляю, я дополнил куском кода в своем вопросе. Но код не перебирает все варианты. Что бы решить эту задачу, надо больше вложенных циклов, я так понимаю?
    – Gubert
    1 мая 2019 в 8:32
  • Код я добавил. Но если нужны не все, лучше, конечно, генерировать только нужные.
    – MBo
    1 мая 2019 в 10:04
  • @MBo, Огромное спасибо! похоже, это именно то, что мне нужно!
    – Gubert
    1 мая 2019 в 11:10
  • @MBo, простите что надоедаю, но мне без Вас никак. Вас не затруднит переделать этот код, для работы со списком? Как оказалось, в моей задаче создание комбинаций будет идти не только по символам, но и по фразам.
    – Gubert
    8 мая 2019 в 13:44

2 ответа 2

0

Число таких комбинаций растёт экспоненциально, поэтому для больших наборов получить всё нереально.

Для генерации комбинаций из наборов разумного размера существует немало возможностей.

Например, можно генерировать комбинации рекурсивно. На K-ом уровне рекурсии используется один K-й символ. Он вставляется во все возможные места имеющихся комбинаций, а также используется вариант без этого символа. Например, на 3 уровень приходят комбинации '', 'a', 'b', 'ab', 'ba'. Для последней из них на следующий уровень передаются 'ba' ('c' не используется), 'cba', 'bca', 'bac'

procedure Generate(s, comb: string; idx: Integer);
var
  i, k: Integer;
  temp: string;
begin
  if idx > Length(s) then begin
    if Length(comb) > 0 then
      Writeln(comb);
    Exit;
  end;

  for k := 1 to Length(comb) + 1 do begin
    temp := comb;
    Insert(s[idx], temp, k);
    Generate(s, temp, idx + 1);
  end;
  Generate(s, comb, idx + 1);
end;

begin
  Generate('abc', '', 1);
  Readln;
end.

Можно также перечислить все ненулевые подмножества входного набора - их будет 2^n-1, и для каждого (размером k) сгенерировать все k! перестановок

0

Вариант "в лоб". Берётся строка длиной k, где k - количество используемых символов.

  1. В k-ю позицию ставится 1-й символ, затем 2-й и т.д.
  2. Когда символы закончатся, в (k-1)-ю позицию ставится 1-й символ, потом повторяется п.1, только теперь пропускаются "ведущие" символы.
  3. Действия повторяются по аналогии пока вариантов не останется.

Пример. символы abc

1. '__a'
2. '__b'
3. '__c'
4. '_ab'
5. '_ac'
6. 'abc'
7. 'bac'
8. 'cab'
9. 'cba'

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.