unique permutations for large sets

Question

I'm trying to find a way to generate unique permutations for x values at y length. What I want to be able to do is something like:

[0,1].unique_permutations(15)
# => [[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
#     [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
#     [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1],
#     ... massive snip
#     [1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 1],
#     [1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 0, 1, 1, 1, 1],
#     ... massive snip
#     [0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
#     [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],

To be clear, I know this is possible:

[0, 0, 0, 1, 1, 1].permutation.count
# => 720
[0, 0, 0, 1, 1, 1].permutation.to_a.uniq.count
# => 20

But this isn't quite the same as what I'm looking for, and performance becomes impractical for long lists:

[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1].permutation.count
# => 479001600 (after a long wait...)
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1].permutation.to_a.uniq.count
# => 1 (didn't actually run this - answer is obvious)

Closest thing I can find is this answer for python, but sadly I don't know python and can't quite figure out how to port that to Ruby.

I'm sure there are other algorithms out there for this type of problem, but I'd really love to keep it in Ruby.

Answer 1

What you're looking for is the n-ary Cartesian product of a set with itself (with n = 15 over set [0, 1] in your example.) This is not the same as the #permutation lists you cite later in the question.

The size of this list grows exponentially with n. For all but tiny n it would be impractical to actually materialize it. You could use a generator instead (forgive my rusty ruby):

class Array
  def cartesian_power(n)
    current = [0] * n
    last = [size - 1] * n

    loop do
      yield current.reverse.collect { |i| self[i] }
      break if current == last

      (0...n).each do |index|
        current[index] += 1
        current[index] %= size

        break if current[index] > 0
      end
    end
  end
end

Then:

>> [0, 1].cartesian_power(3) { |l| puts l.inspect }
[0, 0, 0]
[0, 0, 1]
[0, 1, 0]
[0, 1, 1]
[1, 0, 0]
[1, 0, 1]
[1, 1, 0]
[1, 1, 1]
=> nil

>> %w{a b c}.cartesian_power(2) { |l| puts l.inspect }
["a", "a"]
["a", "b"]
["a", "c"]
["b", "a"]
["b", "b"]
["b", "c"]
["c", "a"]
["c", "b"]
["c", "c"]
=> nil

Answer 2

A recursive solution could look like this (pseudocode, since my Ruby isn't very good):

unique_permutations(n,values) {
    if (n == 0) {
        return EmptyList
    } else {
        lst = unique_permutations(n-1,values)
        newList = EmptyList
        for i in values {
            for j in lst {
                newList.append(prependElementToList(i,j))
            }
        }
        return newList
    }
 }

This could then be called with unique_permutations(15,[0,1])