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.

There are only two permutations of the elements of `{0, 1}`: `0 1` and `1 0`. I'm not sure what you're counting here. — phs, Apr 01 '13 at 02:57
@phs Please see the first code block for the output I'm hoping to achieve. I'm happy to have my terminology corrected if there's a more accurate term for my expected output. — Cade, Apr 01 '13 at 03:02
Would `[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0]` also be in your desired set? Would any length-15 list of `1` and `0` be in it? — phs, Apr 01 '13 at 03:03
@phs Yes. All possible displays of 0 and 1 in the 15 item array. — Cade, Apr 01 '13 at 03:08

score 7 · Accepted Answer · answered Apr 01 '13 at 03:37

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

This is awesome. And thanks for the propert terminology. Now I can go read up on Cartesian products. — Cade, Apr 01 '13 at 11:23

Zach Kemp · Answer 2 · 2013-04-01T03:29:31.967

Here's a thought - for the [0,1] set, you could count up from 0 in binary, and simply insert leading zeros until you have a string of length 15.

n = 15
max = ('1' * n).to_i(2)

(0..max).map do |i|
  i.to_s(2).rjust(n).gsub(" ","0")
end

This result is almost instantaneous to return permuted strings; converting them to arrays of integers (add .split('').map(&:to_i) to the block) takes a second or two more.

This is not a catch-all solution (it assumes that every element of the source array appears at least n times), but it works for your example. It should be translatable to other number bases as well (I think you can go up to base 36 in Ruby).

Edit: well, other number bases may not work so well due their size. But they should give you an idea of exactly how many unique permutations you're looking for; e.g. 3-element of length 15 = 14,348,906, 4 elements is 1,073,741,823 (perhaps someone more familiar with the math can confirm this).

This is a great and very clever answer. Thanks! I wish I could accept two answers, but @phs covered the more general case in my question (x values at y length). — Cade, Apr 01 '13 at 11:27

score 2 · Answer 3 · answered Apr 01 '13 at 03:29

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

score -1 · Answer 4 · answered Jan 16 '15 at 22:02

For anyone still stumbling on this. Since ruby 1.9.2, Array#repeated_permutations does the same.

1.9.2-p320 :056 > 

puts %w(a b c).repeated_permutation(2).map(&:inspect)
["a", "a"]
["a", "b"]
["a", "c"]
["b", "a"]
["b", "b"]
["b", "c"]
["c", "a"]
["c", "b"]
["c", "c"]
 => nil 
1.9.2-p320 :057 >

unique permutations for large sets

4 Answers4