Generate numbers from n to m from a list

Question

I will start with an example; for n = 1 and m = 100 and in the list [1, 2, 3] generate all numbers with 1 digit and two digits and so on, but in this case they should be less than 100.

Output:

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

Then we stop because the following numbers will be more than 100, for example:

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

As you noticed, I add 1, 2, 3, 4 to the number I created earlier, for this I use a recursive function that runs in the for loop for every number in my list, and they work up to the generated numbers more than 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 great if I need to start at 1, but if my starting number is much larger, I still need to start this sequence.

Can someone help me with a solution that will produce the same sequences, but from any starting point, and not from 1, so if, for example, the starting point is 100 and the end is 200, then it will:

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

A solution in any programming language would be nice, but please do not embed the main libraries.

Answer 1

You can go from the “correct” (least significant digit) to the “left” (most significant digit) by tracking two values:

• min , the least valid integer that has the same number of digits as what you have processed so far. So, for example, if you processed trailing 27 , then the smallest valid two-digit integer is 11 .
• max , the least valid integer that has the same number of digits as what you processed so far, and is greater than or equal to what you processed so far. So, for example, if you processed trailing 27 , then the least valid two-digit integer greater than or equal to 27 is 31 .
  • Note that max will not always exist. For example, there is no valid two-digit integer greater than or equal to 70 .

The reason you need min is because if you encounter a digit that is not on the list of allowed digits, then the new max will include the previous min instead of the previous max . (For example, the smallest valid two-digit integer greater than or equal to 02 is 11 , not 12 )

At the end, you return max if it exists; otherwise, you return min , but add the smallest digit from your list.

For example, if this.allowedDigits is a set of allowed digits, we can write (in Java):

 private Integer getAllowedDigitGreaterThanOrEqualTo(final int digit) { for (int result = digit; result < 10; ++result) { if (this.allowedDigits.contains(result)) { return result; } } // digit is bigger than anything in the list: return null; } private int getAllowedNumberGreaterThanOrEqualTo(int n) { int minResult = 0; Integer maxResult = 0; int powerOfTen = 1; while (n > 0) { final int digit = n % 10; n /= 10; minResult = getAllowedDigitGreaterThanOrEqualTo(0) * powerOfTen + minResult; if (maxResult != null && this.allowedDigits.contains(digit)) { maxResult = digit * powerOfTen + maxResult; } else { final Integer newDigit = getAllowedDigitGreaterThanOrEqualTo(digit + 1); if (newDigit == null) { maxResult = null; } else { maxResult = newDigit * powerOfTen + minResult; } } powerOfTen *= 10; } if (maxResult == null) { return getAllowedDigitGreaterThanOrEqualTo(1) * powerOfTen + minResult; } else { return maxResult; } } 

Answer 2

the 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 

<strong> Examples

# one

 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 the mimimum greater than the largest digits_min from the 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 less 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 reducing 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 calling Enumerable # entries (or Enumerate # to_a ).

 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 returned by each_with_object .

 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, two-digit combinations are not created 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 will return 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 3

Since you wrote your sample code in Ruby, you can 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] 

Answer 4

So, this requires the entry of numbers, all combinations of numbers are repeated until it reaches a maximum. You want to adjust them to enable recovery and saving in case of entering non-integer numbers or if for some reason it is impossible to reach a maximum for any reason, but it is a solid structure.

 digits = [1,2,3] max = 100 def possible_numbers(arr, max) loop do arr.product(arr).each do |combo| return arr.uniq if combo.join("").to_i > max arr << combo.join("").to_i end end end possible_numbers(digits, max) 

Output:

 => [1, 2, 3, 11, 12, 13, 21, 22, 23, 31, 32, 33]