CODEWITHSUNDEEP
rubyarrayspermutation
Will Von Wizzlepig
Will Von Wizzlepig

Reputation: 73

Permutations in Ruby - unsure how to handle

I am trying to output an array of 10-element arrays containing permutations of 1 and 2, e.g.:

 [[1,1,1,1,1,1,1,1,1,1],
 [1,1,1,1,1,1,1,1,1,2],
 [1,2,1,2,1,2,1,2,1,2],
 ...etc...
 [2,2,2,2,2,2,2,2,2,2]]

I have done this with smaller arrays, but with (10):

 a = [1,1,1,1,1,1,1,1,1,1,2,2,2,2,2,2,2,2,2,2]
 a = a.permutation(10).to_a
 print a.uniq

...this apparently is too big a calculation- after an hour running, it hadn't completed and the ruby process was sitting on 12GB of memory. Is there another way to come at this?

Upvotes: 2

Views: 562

Answers (4)

Cary Swoveland
Cary Swoveland

Reputation: 110665

Here's another way that is similar to the approach taken by @Myst, except I've used Fixnum#to_s to convert an integer to a string representation of its binary equivalent.

There are 2**n integers with n digits (including leading zeros), when each digit equals 1 or 2 (or equals 0 or 1). We therefore can 1-1 map each integer i between 0 and 2**n-1 to one of the integers containing only digits 1 and 2 by converting 0-bits to 1 and 1-bits to 2.

In Ruby, one way to convert 123 to binary is:

123.to_s(2).to_i      #=> 1111011

As

2**9 #=> 512 
(2**9-1).to_s(2)      #=> "111111111"
(2**9-1).to_s(2).to_i #=> 111111111

we see that when comparing numbers between 0 and 511 (2**9-1), the binary representation of 123 would have two leading zeros. As we need those leading zeros to make the conversion to 1's and 2's, it is convenient to leave the binary representation of each numbers as a string, and pad the string with zeros:

str = 123.to_s(2).rjust(9,'0') #=> "001111011"

That allows us to write: 

str.each_char.map { |c| c.eql?("0") ? 1 : 2 } }
  #=> [1, 1, 2, 2, 2, 2, 1, 2, 2]

We can wrap this in a method:

def combos(n)
  (2**n).times.map { |i| i.to_s(2)
                          .rjust(n,'0')
                          .each_char
                          .map { |c| c.eql?("0") ? 1 : 2 } }
end

combos(1)
  #=> [[1], [2]] 
combos(2)
  #=> [[1, 1], [1, 2], [2, 1], [2, 2]] 
combos(3)
  #=> [[1, 1, 1], [1, 1, 2], [1, 2, 1], [1, 2, 2],
  #    [2, 1, 1], [2, 1, 2], [2, 2, 1], [2, 2, 2]] 
combos(4)
  #=> [[1, 1, 1, 1], [1, 1, 1, 2], [1, 1, 2, 1], [1, 1, 2, 2],
  #    [1, 2, 1, 1], [1, 2, 1, 2], [1, 2, 2, 1], [1, 2, 2, 2],
  #    [2, 1, 1, 1], [2, 1, 1, 2], [2, 1, 2, 1], [2, 1, 2, 2],
  #    [2, 2, 1, 1], [2, 2, 1, 2], [2, 2, 2, 1], [2, 2, 2, 2]] 
combos(10).size
  #=> 1024

Upvotes: 0

Myst
Myst

Reputation: 19221

Edit: Don't use this... it's slower by a factor (10 times slower) then running: b= [1,2]; b.repeated_permutation(10).to_a

What you're looking for is actually a binary permutation array...

So taking that approach, we know we have 2**10 (== 1024) permutations, which translated to the numbers between 0 and 1023.

try this:

1024.times.with_object([]) {|i, array| array << ( ("%10b" % (i-1) ).unpack("U*").map {|v| (v == 49) ? 2 : 1}  ) }

Or this (slightly faster):

(0..1023).each.with_object([]) {|i, array| array << ( (0..9).each.with_object([]) {|j, p| p << (i[j] +1)}  ) }

You take the number of options - 1024. For each option (i) you assign a number (i-1) and extract the binary code that comprises that number.

The binary code is extracted, in my example, by converting it to a string 10 digits long using "%10b" % (i-1) and then unpacking that string to an array. I map that array, replacing the values I get from the string (white space == 32 && zero == 48) with the number 1 or (the number 1 == 49) with the number 2.

Voila.

There should be a better way to extract the binary representation of the numbers, but I couldn't think of one, as I'm running ob very little sleep.

Upvotes: 2

Bartosz Łęcki
Bartosz Łęcki

Reputation: 332

First, check size of that permutation

a.permutation(10).size
 => 670442572800

It's huge. What you can do instead is to use Array#repeated_permutations on smaller array. Check it here:

b = [1, 2] # Only unique elements
b.repeated_permutation(10) # Returns enumerable
b.repeated_permutation(10).to_a # Creates array with all of permutations

Those permutations are already unique (which u can check by printing it size with and without Array#uniq )

Upvotes: 6

Frederick Cheung
Frederick Cheung

Reputation: 84114

The approach you've gone down does indeed generate a lot of data - 20!/10! or about 600 billion arrays. This is clearly very wasteful when the output you are after only has 1024 arrays

what you are after is closer to the product method on array

[1,2].product(*([[1,2]]*9))

The product method produces all the possible combinations by picking one element from each of the receiver and its arguments. The use of splats and the * method on array is just to avoid writing [1,2] 9 times.

Upvotes: 4

Related Questions