Generate numbers from n to m from a list

Question

I'll start with an example; given n = 1 and m = 100 and a list [1, 2, 3] generate all numbers with 1 digit and two digits and so on but they need to be less then 100 in this case.

Output:

- 1, 2, 3, 11, 12, 13, 21, 22, 23, 31, 32, 33

Then we stop because the next numbers will over 100, e.g:

- 111, 112, 113, 121, 122, 123, 131, 132, 133, 21..,. 22..., 23..., 31, 32, 33

As you noticed I am appending 1, 2, 3, 4 to a number created before, to do this I am using a recursive function, which is started in a for loop for each number in my list, and they it runs till the generated numbers are greater then my limit.

def x(str, finish, d, c) 
  return if d >= finish
  [1, 2, 3, 4].each do |e|
    x(str, end, d*c+e)
  end

  # do something if d >= str
end

This works fine if I need to start from 1, but if my starting number is a lot bigger, I still need to start to create this sequence.

Can somebody help me with a solution that will produce the same sequences, but from any starting point rather then 1, so if for example the starting point was 100 and end 200 the output will be:

111, 112, 113, 114, 121, 122, 123, 124, 131, 132, 132 [...]

A solution in any programming language would be nice, but please not builtin core libraries.

Answer 1

Code

def generate_em(minimum, maximum, list)
  digits_min = minimum.to_s.size
  digits_min += 1 if minimum > (list.max.to_s*digits_min).to_i
  digits_max = maximum.to_s.size
  digits_max -= 1 if maximum < (list.min.to_s*digits_max).to_i
  (digits_min..digits_max).each_with_object([]) { |n,arr|
    arr.concat(list.repeated_permutation(n).to_a.map { |a| a.join.to_i }) }.
      uniq.
      select { |n| (minimum..maximum).cover?(n) }
end

Examples

#1

minimum =   1
maximum = 100
list = [1, 2, 3]

generate_em(minimum, maximum, list)
  #=> [1, 2, 3, 11, 12, 13, 21, 22, 23, 31, 32, 33] 

#2

minimum = 78
maximum = 3332
list = [3, 4, 5, 6, 7]

generate_em(minimum, maximum, list)
  #=> [333, 334, 335, 336, 337, 343, 344, 345, 346, 347, 353, 354, 355, 356,
  #    357, 363, 364, 365, 366, 367, 373, 374, 375, 376, 377, 433, 434, 435,
  #    436, 437, 443, 444, 445, 446, 447, 453, 454, 455, 456, 457, 463, 464,
  #    465, 466, 467, 473, 474, 475, 476, 477, 533, 534, 535, 536, 537, 543,
  #    544, 545, 546, 547, 553, 554, 555, 556, 557, 563, 564, 565, 566, 567,
  #    573, 574, 575, 576, 577, 633, 634, 635, 636, 637, 643, 644, 645, 646,
  #    647, 653, 654, 655, 656, 657, 663, 664, 665, 666, 667, 673, 674, 675,
  #    676, 677, 733, 734, 735, 736, 737, 743, 744, 745, 746, 747, 753, 754,
  #    755, 756, 757, 763, 764, 765, 766, 767, 773, 774, 775, 776, 777] 

#3

minimum = 0
maximum = 100
list = [0, 1, 2]

generate_em(minimum, maximum, list)
  #=> [0, 1, 2, 10, 11, 12, 20, 21, 22, 100]

Explanation

Example #1

The steps for the first example above are as follows.

digits_min = minimum.to_s.size
  #=> 1 

Increase digits_min by one if mimimum is larger than the largest digits_min digits from list.

digits_min += 1 if minimum > (list.max.to_s*digits_min).to_i
digits_min
  #=> 1 

digits_max = maximum.to_s.size
  #=> 3 

Decrease digits_max by one if maximum is smaller than the smallest digits_max digits from list.

digits_max -= 1 if maximum < (list.min.to_s*digits_max).to_i
digits_max
  #=> 2

We improve efficiency by having reduced digits_max from 3 to 2

c = digits_min..digits_max
  #=> 1..2 
d = c.each_with_object([])
  #=> #<Enumerator: 1..2:each_with_object([])> 

We can see the elements that will be generated by this enumerator by invoking Enumerable#entries (or Enumerable#to_a) on it.

d.entries
  #=> [[1, []], [2, []]]

n, arr = d.next
  #=> [1, []] 
n #=> 1 
arr
  #=> [] 
e = list.permutation(n)
  #=> #<Enumerator: [1, 2, 3]:permutation(2)>
f = e.to_a
  #=> [[1], [2], [3]] 
arr.concat f
  #=> [[1], [2], [3]] 
n, arr = d.next
  #=> [2, [[1], [2], [3]]] 
n #=> 2 
arr
  #=> [[1], [2], [3]] 
e = list.permutation(n)
  #=> #<Enumerator: [1, 2, 3]:permutation(2)> 
f = e.to_a
  #=> [[1, 2], [1, 3], [2, 1], [2, 3], [3, 1], [3, 2]] 
arr.concat f
  #=> [[1], [2], [3], [1, 2], [1, 3], [2, 1], [2, 3], [3, 1], [3, 2]] 

arr is returned by each_with_object's block.

g = arr.map { |a| a.join.to_i }
  #=> [1, 2, 3, 12, 13, 21, 23, 31, 32]
h = g.uniq
  #=> [1, 2, 3, 12, 13, 21, 23, 31, 32]
h.select { |n| (minimum..maximum).cover?(n) }
  #=> [1, 2, 3, 12, 13, 21, 23, 31, 32]

Example #2

In the second example no two-digit combinations are generated because

78 > (list.max.to_s*2).to_i
  #=> 78 > 77 => true

and no four-digit combinations are generated because

3332 < (list.min.to_s*4).to_i
  #=> 3332 < 3333 => true 

Example #3

Without uniq, the method would have returned duplicate values:

[0, 1, 2, 0, 1, 2, 10, 11, 12, 20, 21, 22, 0, 1, 2, 10, 11, 12, 20, 21, 22, 100]

Answer 2

Since you wrote your example code in Ruby, you could use repeated_permutation :

def possible_numbers(arr, min, max)
  min_digits = min.to_s.size
  max_digits = max.to_s.size
  (min_digits..max_digits).flat_map do |i|
    arr.repeated_permutation(i)
       .map { |digits| digits.join.to_i }
       .select { |number| number >= min && number <= max }
       .uniq
  end
end

p possible_numbers([1, 2, 3], 100, 200)
# => [111, 112, 113, 121, 122, 123, 131, 132, 133]