Select array permutations where pattern elements match rule

Question

Given an array ary of five elements:

ary = [true, true, true, false, false]

I want to take all permutations of ary where the two false values are non-consecutive, considering that the last position (index 4) wraps around to the first (index 0):

[true, false, true, false, true] #=> Selected
[true, true, false, true, false] #=> Selected
[false, true, true, true, false] #=> Rejected

I thought the answer might come down to select and each_with_index methods. I'm not sure how to relate the elements in the array using logical expressions.

Cary Swoveland · Accepted Answer · 2017-02-20T22:00:59.383

This recursive method generates the permutations directly, as opposed to generating large numbers of permutations and discarding those that do not satisfy the specification.

Code

def all_perms(arr_size, nbr_false)
  return nil if nbr_false > arr_size/2
  return [true]*arr_size if nbr_false.zero?
  recurse(arr_size, nbr_false, true)
end

def recurse(arr_size, nbr_false, full_arr)
  last_first = arr_size + 1 - 2*nbr_false
  (0..last_first).each_with_object([]) do |i,a|
    pre = [true]*i << false
    case nbr_false
    when 1
      a << pre + [true]*(arr_size-pre.size)
    else
      pre << true
      sub_arr_size = arr_size - pre.size - (i.zero? && full_arr ? 1 : 0)
      post = [true]*(arr_size-pre.size-sub_arr_size)
      recurse(sub_arr_size, nbr_false-1, false).each { |aa| a << pre + aa + post }
    end
  end
end

Examples

arr_size  = 5
nbr_false = 2

b = all_perms(arr_size, nbr_false)
  #=> [[false, true, false, true, true],
  #    [false, true, true, false, true],
  #    [true, false, true, false, true],
  #    [true, false, true, true, false],
  #    [true, true, false, true, false]]
b == b.uniq
  #=> true
b.any? { |a| a.each_cons(2).any? { |x,y| x == false && y == false} }
  #=> false
b.any? { |a| a.first == false && a.last == false }
  #=> false

arr_size  = 8
nbr_false = 3

b = all_perms(arr_size, nbr_false)
  #=> [[false, true, false, true, false, true, true, true],
  #    [false, true, false, true, true, false, true, true],
  #    [false, true, false, true, true, true, false, true],
  #    [false, true, true, false, true, false, true, true],
  #    [false, true, true, false, true, true, false, true],
  #    [false, true, true, true, false, true, false, true],
  #    [true, false, true, false, true, false, true, true],
  #    [true, false, true, false, true, true, false, true],
  #    [true, false, true, false, true, true, true, false],
  #    [true, false, true, true, false, true, false, true],
  #    [true, false, true, true, false, true, true, false],
  #    [true, false, true, true, true, false, true, false],
  #    [true, true, false, true, false, true, false, true],
  #    [true, true, false, true, false, true, true, false],
  #    [true, true, false, true, true, false, true, false],
  #    [true, true, true, false, true, false, true, false]] 

b == b.uniq
  #=> true
b.any? { |a| a.each_cons(2).any? { |x,y| x == false && y == false} }
  #=> false
b.any? { |a| a.first == false && a.last == false }
  #=> false

Notes

The valid permutations are the same for all arrays of a given size that contain the same number of false elements. I therefore made the arguments of all_perms the size of the desired array and the number of false elements it is to contain (the other elements all being true).
The third argument of recurse, full_arr, is a boolean that equals true when recurseis called from all_perms but equals false when recurse is called from recurse. This was necessary to avoid permutations that start and end with false (the cycling condition that is to be avoided). When full_arr is true and i #=> 0, the last element of the sub-array being constructed must be true. In all other situations it may be true or false.
The index i refers to the index of the sub-array being constructed at which the first false is located. If, for example, arr_size #=> 4, nbr_false #=> 2 and full_arr #=> false, the index i of the first false can be 0 or 1. It cannot be 2, as that would require the last two elements to be false.

Nice. Do you know any generic method to calculate all the unique permutations of an array with non-unique elements? — Eric Duminil, Feb 20 '17 at 22:15
@Eric, in general, no, but I'm sure there's an authoritative answer out there. In the case where, as here, `arr.uniq.size #=> 2`, we can reason as follows. Let `n` be the array size, `m` be the number of `false` elements and `n-m` be the number of `true` elements. There are `n` permutations of the elements of the array. Consider any one of those. Think of each of the `false`s as wearing a different coloured hat. How many ways can we rearrange the hats, keeping the same positions in the array. That would be `m!` (cont...) — Cary Swoveland, Feb 20 '17 at 22:54
...For each of those, how many ways can the `n-m` `true`s be rearranged, keeping the same positions in the array? That's `(n-m)!`. So the same permutation can be generated `m!(n-m)!` ways. Therefore, the number of unique permutations is `n!/(m!(n-m)!)`. Does that expression look familiar? — Cary Swoveland, Feb 20 '17 at 22:54
Thanks for the explanation. I wasn't looking for the number of permutations but for the permutations themselves. I found this nice piece of [Python code](http://stackoverflow.com/questions/12836385/how-can-i-interleave-or-create-unique-permutations-of-two-stings-without-recurs/12837695#12837695), adapted from Knuth's book. I wrote a Ruby Enumerator based on this code. It needs elements to be comparable, though, which isn't the case with standard Ruby booleans. — Eric Duminil, Feb 20 '17 at 22:57
@CarySwoveland This is really amazing, thank you for giving me so much detail to learn from. Your approach of writing methods to allow changes to the arguments in the future is something I hope to emulate — zqe, Feb 21 '17 at 04:47

Eric Duminil · Answer 2 · 2017-02-20T09:50:43.073

Solution #1

The obvious example for one such array is :

[true,false,true,false,true]

If you switch one false with the middle true, the array isn't valid anymore.

If you switch one false with the left or right true, you get the same array, rotated left or right.

So to get all the possible arrays, you just need :

base_array = [true,false,true,false,true]
Array.new(5){ |i| base_array.rotate(i) }

It outputs :

[[true, false, true, false, true],
 [false, true, false, true, true],
 [true, false, true, true, false],
 [false, true, true, false, true],
 [true, true, false, true, false]]

Solution #2

The bruteforce solution would to create every unique permutation of ary and check that no consecutive elements are both false. To account for the wrap, the first element is appended to the array :

ary = [true, true, true, false, false]
ary.permutation.to_a.uniq.select do |a|
  (a + [a.first]).each_cons(2).all? { |x, y| x || y } 
end

If you want to get fancy, you could write :

ary = [true, true, true, false, false]
n = ary.size
ary.permutation.to_a.uniq.select do |a|
  a.cycle.take(n+1).each_cons(2).all?(&:any?)
end

This is brilliant, so useful to see different ways to solve a problem that was giving me a conceptual challenge. Thanks for offering two different approaches! — zqe, Feb 21 '17 at 04:59

score 0 · Answer 3 · answered Feb 20 '17 at 04:18

The quick and dirty method might be to expand the arrays to account for the wrapping:

array = [ true, true, true, false, false ]

array.permutation.to_a.uniq.map do |set|
  [ set[-1] ] + set + [ set[0 ] ]
end.select do |set|
  set.chunk_while { |b,a| b == a }.all? do |chunk|
    chunk[0] == true or chunk.length == 1
  end
end.map do |set|
  set[1, set.length - 2]
end

This yields:

# => [
#   [true, true, false, true, false],
#   [true, false, true, true, false],
#   [true, false, true, false, true],
#   [false, true, true, false, true],
#   [false, true, false, true, true]]

Wow thank you- this is a really cool way for me to learn how to apply some methods I haven't used before — zqe, Feb 21 '17 at 04:54

sawa · Answer 4 · 2017-02-20T12:02:40.657

0

Without any smart consideration, one way is:

ary.permutation
.to_a.uniq
.reject do
  |a|
  i, j = a.each_index.select{|i| a[i] == false}
  (i + 1) == j || j - 4 == i
end

edited Feb 20 '17 at 12:02

answered Feb 20 '17 at 05:20

sawa

165,429
45
277
381

Thank you! This is really neat. I'm not sure I understand what you mean by "smart consideration", is it possible for you to say more about that? – zqe Feb 21 '17 at 04:54

Select array permutations where pattern elements match rule

4 Answers4

Solution #1

Solution #2