Как получить все комбинации массива с общим размером?

Question

У меня есть массив, подобный [1, -1,0], и я хочу сгенерировать вектор всех комбинаций с этими элементами массива и общим размером. Например, размер: 3 и положить: [1 1 1] [1 1 0] [1 1 -1] ... [0 0 0] или размер: 4 и вывод: [1 1 1 1] [1 1 1 0] ... [0 0 0 0] или другой размер и другой массив.

Как сделать это с универсальным массивом и общим размером?

Answer 1

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

const append = (xs, x) =>
  xs .concat ([ x ])

const ncomb = function* (n, xs = [])
{ const gen = function* (n, acc)
  { if (n === 0)
      yield acc
    else
      for (const x of xs)
        yield* gen (n - 1, append (acc, x))
  }
  yield* gen (n, [])
}

const data =
  [ 1, 2, 3 ]

const print = (...xs) =>
  console.log (...xs.map (x => JSON.stringify (x)))

print
  ( Array.from (ncomb (0, data))
    // [[]]
    
  , Array.from (ncomb (1, data))
    // [[1],[2],[3]]
    
  , Array.from (ncomb (2, data))
    // [[1,1],[1,2],[1,3],[2,1],[2,2],[2,3],[3,1],[3,2],[3,3]]
    
  , Array.from (ncomb (3, data))
    // [[1,1,1],[1,1,2],[1,1,3],[1,2,1],[1,2,2],[1,2,3],[1,3,1],[1,3,2],[1,3,3],[2,1,1],[2,1,2],[2,1,3],[2,2,1],[2,2,2],[2,2,3],[2,3,1],[2,3,2],[2,3,3],[3,1,1],[3,1,2],[3,1,3],[3,2,1],[3,2,2],[3,2,3],[3,3,1],[3,3,2],[3,3,3]]
  )

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

const prepend = (xs, x) =>
  [ x ] .concat (xs)

print
  ( Array.from (ncomb (3, data))
    // [[1,1,1],[2,1,1],[3,1,1],[1,2,1],[2,2,1],[3,2,1],[1,3,1],[2,3,1],[3,3,1],[1,1,2],[2,1,2],[3,1,2],[1,2,2],[2,2,2],[3,2,2],[1,3,2],[2,3,2],[3,3,2],[1,1,3],[2,1,3],[3,1,3],[1,2,3],[2,2,3],[3,2,3],[1,3,3],[2,3,3],[3,3,3]]
  )