Алгоритм логики, расщепление массивов

Question

Я не ищу решение, просто псевдокод или логику, которые помогли бы мне получить ответ.

Учитывая массив:

[1,2,3,4]

Я хочу разделить это на два массива различной длины и содержимого, сумма длин которых равна длине данного массива. Это было бы идеально без повторения.

Пример вывода:

 [[1],[2, 3, 4]]  
 [[1, 2], [3, 4]]  
 [[1, 3], [2, 4]]  
 [[1, 4],[2, 3]]  
 [[1, 2, 3], [4]]
 [[2], [1, 3, 4]]
 [[2, 4], [1, 3]]
 [[3], [1, 2, 4]]

Еще пример:

[[1, 3, 4, 6, 8], [2, 5, 7]] //this is a possible combination of 1 through 8 
                             //array

Интуиция: Первая попытка состояла в том, чтобы поместить массив начальных чисел [i] в ​​массив результатов [0], а второй цикл переместил индекс для третьего цикла, чтобы начать итерацию в том виде, в каком он захвачен. Затем заполните другой список оставшимися индексами. Был плохо зачат ...

Вторая идея - перестановки. Напишите алгоритм, который реорганизует массив во все возможные комбинации. Затем выполните одну и ту же операцию разделения для этих списков с разными индексами, отслеживая уникальные списки в виде строк в словаре.

[1,2,3,4,5,6,7,8]
  ^
split
[1,2,3,4,5,6,7,8]
    ^
  split
[1,3,4,5,6,7,8,2]
  ^
 split

Я уверен, что это создаст списки, которые я ищу. Тем не мение! Я боюсь, что это может быть менее эффективно, чем хотелось бы, из-за необходимости сортировки, когда проверка на дубликаты и перестановки в первую очередь дорогая.

Пожалуйста, ответьте, как бы вы подошли к этой проблеме и почему.

Answer 1

псевдокод.Идея состоит в том, чтобы начать с одного предмета в одной из сумок, а затем поместить следующий предмет один раз в одну сумку, один раз в другой.

function f(A):
  // Recursive function to collect arrangements
  function g(l, r, i):
    // Base case: no more items
    if i == length(A):
      return [[l, r]]

    // Place the item in the left bag
    return g(l with A[i], r, i + 1)
      // Also return a version where the item
      // is placed in the right bag
      concatenated with g(l, r with A[i], i + 1)

  // Check that we have at least one item
  if A is empty:
    return []

  // Start the recursion with one item placed
  return g([A[0]], [], 1)

(PS см. редакции для кода JavaScript.)