перестановка в списке с повторением ocaml

Question

У меня есть функция, которая делает комбинации из K различных объектов, выбранных из N элементов списка, проблема не в том, чтобы повторяться, например:

extract 2 ["a"; "б ";" с "" d "] ;;-: список строк списка = [["a";"Б"];[ "А";"С"];[ "А";"Г"];[ "B";"С"];[ "B";"Г"];[ "С";"d"]]

Вот мой код:

# let rec extract k list =
if k <= 0 then [ [] ]
else match list with
     | [] -> []
     | h :: tl ->
        let with_h = List.map (fun l -> h :: l) (extract (k-1) tl) in
        let without_h = extract k tl in
        with_h @ without_h;;

Я пытаюсь понять, как это сделать, спасибо за ответ.

Answer 1

У меня есть функция, которая создает комбинации из K различных объектов

Действительно.

проблема не в том, чтобы повторяться,

Это не намного сложнее, чем комбинации.Есть два способа сделать свой индуктивный шаг.Если вы хотите переставить k элементы (не пустого) набора A, вы можете:

Метод 1

Для каждого элемента x вA, вычислите перестановки k-1 элементов A\{x} и поместите x перед всеми этими перестановками.Затем объедините наборы решений, которые вы получили для каждого x.

Метод 2

Выберите один x в A, рассчитайте перестановки k-1 элементы A\{x}, затем для каждой найденной перестановки вычислите новые, вставив x в каждую возможную позицию.