3

Sometimes I need a way to do this, and wonder if this is a common problem or method and has a name to it:

Such as, we want to iterate through all cases of 4 dice, or iterate through all cases of 20 slots, and each slot can fit in any number from 0 to 50.

So the requirement is given N, the size of the array, such as N = 4, and a "range" such as from 1 to 6, and we do a Iterator.new(4, 1..6) and get back:

[1, 1, 1, 1]

and have a way to do iterator.next() and get back

[1, 1, 1, 2]

and keep on doing iterator.next() will get us

[1, 1, 1, 6]

and the next iterator.next() will get us

[1, 1, 2, 1]

which is like 6 + 1 and it can't hold it, so it resets to 1 and carry over to the next digit.

and iterator.next() will finally get to

[6, 6, 6, 6]

and the next iterator.next() will get us

false  (or nil)

Does this problem have a common name in computer science, and what might be a simple way to do it in Ruby?

Right now I am trying to do it using recursion, and it seems complicated:

n = 4
a = 1
b = 6

arr = [a] * 4

def increment_position(arr, a, b, pos)

    return false if (pos >= arr.length)

    arr[-1 - pos] += 1

    if arr[-1 - pos] > b
        arr[-1 - pos] = a
        return increment_position(arr, a, b, pos + 1)
    else
        return arr
    end

end

def get_next_iteration(arr, a, b)
    return increment_position(arr, a, b, 0)
end

loop do
    p arr
    break if !get_next_iteration(arr, a, b)
end

P.S. The solution should not use too much memory, such as just bytes, or kilobytes, or MB. For example, it should be able to handle Iterator.new(5, 0..50) or Iterator.new(6, 0..50) easily.

nonopolarity
  • 146,324
  • 131
  • 460
  • 740
  • You needn't be concerned about the enumerator using too much memory, as it's merely a rule. For example, `arr = [1,2,3]; enum = arr.to_enum; 3.times { puts enum.next } #=> 1 2 3; enum.rewind; arr.replace([4,5,6]); 3.times { puts enum.next } #=> 4 5 6`. – Cary Swoveland Nov 22 '15 at 21:28
  • ...cont. This is @kdole's [suggestion](http://stackoverflow.com/questions/7220896/get-current-ruby-process-memory-usage) for determining the memory use of the current Ruby process in bytes: `def mem_use() \`ps -o rss -p #{$$}\`.strip.split.last.to_i * 1024 end`. Consider the following: `puts mem_use #=> 8232960; a = 1_000_000.times.to_a; puts mem_use #=>16498688; enum = a.to_enum; puts mem_use #=> 16498688; 1_000_000.times { enum.next }; puts mem_use #=> 16535552`. – Cary Swoveland Nov 22 '15 at 21:48
  • I was concerned because one answer that would work with small numbers, but with either `product_range_enumerator(5, 0..50)` or `product_range_enumerator(6, 0..50)` it actually hanged my Macbook Pro – nonopolarity Nov 22 '15 at 22:17
  • For your specific example, you could write: `s = '-1'; enum = Enumerator.new { |e|; (6**4).times { e << (s = (s.to_i(6)+1).to_s(6); s.each_char.map(&:next).join.rjust(4,'1').split('')) }}`. – Cary Swoveland Nov 22 '15 at 22:46

3 Answers3

6

So, you basically want the cartesian product of a Range with itself. That's easy to do:

def product_range_enumerator(num, range)
  range.to_a.product(*([range.to_a] * num.pred)).each
end

product_range_enumerator(4, 1..6)
# => #<Enumerator: ...>

enum = product_range_enumerator(4, 1..6)

enum.next
# => [1, 1, 1, 1]

enum.next
# => [1, 1, 1, 2]

# …

enum.next
# => [1, 1, 1, 6]

enum.next
# => [1, 1, 2, 1]

# …

enum.next
# => [6, 6, 6, 6]

enum.next
# StopIteration: iteration reached an end
Jörg W Mittag
  • 363,080
  • 75
  • 446
  • 653
  • I will add to the original question that the requirement should be it is not memory intensive. For example, the example above, with 2 lines: `enum = product_range_enumerator(4, 0..50); sleep 60;` and the ruby app will show it is using 700MB of memory on Mac OS X's Activity Monitor. If I change it to `enum = product_range_enumerator(5, 0..50);` it was eating up 20GB of memory and the Macbook wasn't very responsive either (I am using Ruby 2.0.0) – nonopolarity Nov 22 '15 at 17:15
3

AKA as permutations with repetition

iterator = (1..6).to_a.repeated_permutation(4)

#demo:
7.times{p iterator.next}

#[1, 1, 1, 1]
#[1, 1, 1, 2]
#[1, 1, 1, 3]
#[1, 1, 1, 4]
#[1, 1, 1, 5]
#[1, 1, 1, 6]
#[1, 1, 2, 1]

iterator2 = (0..50).to_a.repeated_permutation(6) #no problem
steenslag
  • 79,051
  • 16
  • 138
  • 171
1

From first principles:

def range_enumerator(rng, n)
  Enumerator.new do |e|
    offsets = [*0...n]
    sz = rng.size**n
    arr = [rng.first]*n
    sz.times do
      e << arr
      i = offsets.rindex { |i| arr[i] < rng.last }
      break unless i
      arr[i] += 1
      (i+1...n).each { |j| arr[j] = rng.first } if i < n-1
    end
  end
end

rng = 1..6
n = 4
enum = range_enumerator(rng, n)

count = 0
no_print = (7..rng.size**n-4)
loop do
  e = enum.next
  puts "#{count}: #{e}" unless no_print.cover?(count)
  count += 1
 # puts "count=#{count}"
end
  # 0:    [1, 1, 1, 1]
  # 1:    [1, 1, 1, 2]
  # 2:    [1, 1, 1, 3]
  # 3:    [1, 1, 1, 4]
  # 4:    [1, 1, 1, 5]
  # 5:    [1, 1, 1, 6]
  # 6:    [1, 1, 2, 1]
  # 1293: [6, 6, 6, 4]
  # 1294: [6, 6, 6, 5]
  # 1295: [6, 6, 6, 6]
Cary Swoveland
  • 106,649
  • 6
  • 63
  • 100
  • thanks. what is "first principles"? is this how to write an Enumerator? That is, have a function that return `Enumerator.new`, which is the new Enumerator object with some logic in it? – nonopolarity Nov 22 '15 at 22:12
  • your `no_print.cover?(count)` is an interesting way to skip over a chunk of output – nonopolarity Nov 22 '15 at 22:21
  • Many enumerators are produced by Ruby's built-in methods, but you can create you own with the class method [Enumerator::new](http://ruby-doc.org/core-2.1.5/Enumerator.html#method-c-new). That's what I meant by "first principles", but that was a poor choice of words. I should have said, "Create a custom iterator:". – Cary Swoveland Nov 23 '15 at 18:46