Получите декартово-подобный продукт списка списков с неравной длиной и функцией (список 'a ->' b), примененной к каждому элементу.

Question

Я уже давно борюсь с этим.Хотя у меня был какой-то длинный императивный метод, который работал, я решил изменить дизайн этой части:

• Взять список списков

• Составить список первого элемента каждого подсписказатем снова первый элемент, но из последнего подсписка второй элемент, затем третий, пока этот последний список не будет исчерпан, проделайте то же самое для N-1 подсписка, который в основном дает своего рода произведение всех этих списков

  Другими словами: [abc][FG][98] следует оценивать как (примените функцию f к каждому элементу, запятые предназначены для удобства чтения): [aF9, aF8, aG9, aG8, bF9, bF8, bG9, bG8, cF9,cF8, cG9, cG8]

• Свести это и применить функцию к каждому элементу результата, которая сама возвращает список

• Эти списки затем сглаживаютсявернуть односвязный список
• Когда подсписок пуст (вызовите это E), тогда оцениваются только подсписки 0 .. E-1 (не в моем примере)

Вот рабочий примеркоторый ясно показывает его рекурсивный характер, но, очевидно, идет только как дВот три списка:

let rec nestedApply f inp =
    match inp with
    | [] -> []
    | [x] -> x |> List.collect f
    | [x;y] -> 
        x
        |> List.collect (fun a -> y |> List.collect (fun b -> [a;b]))
        |> List.collect f
    | [x;y;z] -> 
        x
        |> List.collect (fun a -> y |> List.collect (fun b -> z |> List.collect (fun c -> [a;b;c])))
        |> List.collect f
    | head::tail ->
        // ??? I gave the following several attempts but couldn't get it right
        nestedApply f tail
        |> List.collect (fun a -> a::head)
        |> List.collect f

Я бы предпочел решение, которое не взорвало стек.В конце концов мне понадобится lazy-eval, так что я, вероятно, прибегну к последовательностям, но со списками я думаю, что алгоритм будет проще думать.

Пример: nestedApply (fun a -> [a]) [[1 .. 5];[6;7];[11;12]]

Примерoutput:

[1; 6; 11; 1; 6; 12; 1; 7; 11; 1; 7; 12; 2; 6; 11; 2; 6; 12; 2; 7; 11; 2; 7;
 12; 3; 6; 11; 3; 6; 12; 3; 7; 11; 3; 7; 12; 4; 6; 11; 4; 6; 12; 4; 7; 11; 4;
 7; 12; 5; 6; 11; 5; 6; 12; 5; 7; 11; 5; 7; 12]

В качестве отступления, поскольку это выглядит довольно "нормальным" алгоритмом, хотя он не является декартовым произведением, к какому типичному общеизвестному алгоритму это относится ближе всего?

Answer 1

Спасибо @ vivek_23 за предоставление указателей на N-арные деревья, я прочитал несколько постов о обходе деревьев и тому подобном, что не совсем то, о чем идет речь (пожалуйста, поправьте меня, если я ошибаюсь), но этопривести меня к простому и, я считаю, элегантному решению:

let rec nestedApply f acc inp =
    match inp with
    | [] -> f acc
    | head::tail -> 
        [
            for x in head do
                yield! nestedApply f (x::acc) tail
        ]

В этом случае функция apply f действует на небольшие подсписки, которые имеют одинаковую длину на каждой итерации, но дляв моем конкретном случае это не имело значения (кроме того, оно ускорило процесс, если функции apply не нужно заботиться о порядке подмножеств).Чтобы получить точно такое же поведение, как в исходном вопросе, используйте его следующим образом:

> nestedApply List.rev [] [[1 .. 5];[6;7];[11;12]];;
val it : int list =
  [1; 6; 11; 1; 6; 12; 1; 7; 11; 1; 7; 12; 2; 6; 11; 2; 6; 12; 2; 7; 11; 2; 7;
   12; 3; 6; 11; 3; 6; 12; 3; 7; 11; 3; 7; 12; 4; 6; 11; 4; 6; 12; 4; 7; 11; 4;
   7; 12; 5; 6; 11; 5; 6; 12; 5; 7; 11; 5; 7; 12]

Слегка аккуратное решение скрывает аккумулятор:

let nestedApply f inp =
    let rec innerLoop acc inp =
        match inp with
        | [] -> f acc
        | head::tail -> 
            [
                for x in head do
                    yield! innerLoop (x::acc) tail
            ]

    innerLoop [] inp

Answer 2

_{(примечание ОП: этот ответ высокого уровня привел к моей реализации в другом ответе, спасибо Вивек!)}

• Данныенабор, который у вас есть, называется N-арным деревом.

• Здесь каждый элемент узла / списка может иметь число дочерних элементов от 0 <= children <= N.

Шаги алгоритма:

• Пробежаться по первому списку lists.
• Применить глубина первого поиска каждому элементу в списке.
• Заставить дочерние элементы возвращать себя как list.
• Создайте новый пустой lists на родительском уровне и добавьте родительский элемент в каждый возвращенный дочерний список и добавьте его в lists.
• Возвращает lists.

Псевдокод:

function possibleLists(curr_list){
  my_new_lists = [];
  for each element in curr_list:
     child_lists = possibleLists(element)
     for each child_list in child_lists:
         child_list.add(element)
         my_new_lists.add(child_list)    
     if child_lists.size() == 0: // needed if there were no further deep levels than the level of curr_list elements
         my_new_lists.add(new List().add(child_list)) // you can return current instance to have this kind of chaining.      

  return my_new_lists;
}

Примечание: Если вы хотите достичь хвостовой рекурсии, то вам придется пройти путь элементов, посещенных кследующий рекурсивный вызов параметров в виде list, который будет добавлен в его дочерние элементы.

PS - я не кодер F#, поэтому могу помочь вам с максимальным псевдокодом.