How to get all combinations of an array with gener

2019-07-27 14:51发布

问题:

I have an array like [1,-1,0] and I want to generate all combinations vector with this array items and generic size. For example size: 3 and out put: [1 1 1] [1 1 0] [1 1 -1] ... [0 0 0] or size: 4 and output: [1 1 1 1] [1 1 1 0] ... [0 0 0 0] or another size and another array.

How to make it with generic array and generic size?

回答1:

You mentioned JavaScript so here's one way using generators

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]]
  )

Above the combinations increment the rightmost element, but this ordering can be changed. If you change the append operation to prepend you will generate combinations where the leftmost element increments instead –

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]]
  )