Реализация алгоритма сочетаний без повторений С#

Question

Само задание выглядит так:

С клавиатуры ввести элементы алфавита, например: a, b, c, d.
Задать длину слов N, которые формируются из заданного алфавита.
Подсчитать сколько таких слов без повторений букв можно получить.
Вывести на экран все возможные слова, которые можем получить из заданного алфавита заданной длины. Например при N=3: abc, bcd, cda, dab, ….. и так далее.

Я реализовала лишь 1-3 пункты, но над 4-м я уже 3 дня думаю. Алгоритмы, которые я пишу, в итоге разрастаются до ужасных размеров с кучей вложенных циклов и метками... Я сдаюсь. Помогите, пожалуйста.

Answer 1

В данном случае требуется вывести все размещения по k из n элементов.

Размещения в лексикографическом порядке нетрудно сгенерировать рекурсивно - вставляя на текущую позицию очередной комбинации по очереди все ещё пока неиспользованные элементы (и помечая, что они использованы - для следующих уровней рекурсии). Результат можно использовать как индексы в наборе введённых символов (102 => bac для алфавита abcd)

Кода вы не привели, отталкиваться мне не от чего, поэтому пишу, на чём удобнее:

const
  n = 5;
  k = 3;
var
  Arrangement: array[0..k-1] of Byte;
  Used: set of Byte;

  procedure GenArrangement(position: Integer);
  var
    i: Byte;
    s: string;
  begin
    if position = k then begin // комбинация заполнена, выводим
      s := '';
      for i := 0 to k-1 do
        s := s + IntToStr(Arrangement[i]);
      Writeln(s);
    end else
      for i := 0 to n - 1 do
        if not(i in Used) then
        begin
          Used := Used + [i];
          Arrangement[position] := i;
          GenArrangement(position + 1);
          Used := Used - [i];
        end;
  end;

begin
  Used := [];
  GenArrangement(0);

012
013
014
021
023
024
031
032
034
041
042
043
102

...
430
431
432

БЛОГ НА HUSL

Реализация алгоритма сочетаний без повторений С#

Ответы (1 шт):