All kinds of permutations with the condition

Question

I'm wondering if there is an elegant way in Ruby to come up with all the permutations (with repetitions) of some integers with requirements that: 1) the entered values ​​should be in ascending order from left to right 2) Zero is exempted from this rule.

Below I have a subset of the output for three digits and integers 0,1,2,3,4,5,6,7,8,9. This is just a subset of the complete answer, and in particular it is a subset that starts with 5. I included notes on a couple of them

500 - Zero is used twice 505 - 5 is used twice. Note that 504 is not included because 5 was introduced on the left and 4 < 5 506 507 508 509 550 555 556 557 558 559 560 565 - Though 5 < 6, 5 can be used twice because 5 was introduced to the left of 6. 566 567 568 569 570 575 577 578 579 580 585 588 589 590 595 599 

I need to be able to do this for an arbitrarily long output length (not just 3, like this example), and I need to be able to do this for specific sets of integers. However, zero will always be an integer to which the order rule does not apply.

Answer 1

This will work:

 class Foo include Comparable attr :digits def initialize(digits) @digits = digits.dup end def increment(i) if i == -1 # [9,9] => [1,0,0] @digits.unshift 1 else succ = @digits[i] + 1 if succ == 10 # [8,9] => [9,0] @digits[i] = 0 increment(i-1) else @digits[i] = @digits[0,i].sort.detect { |e| e >= succ } || succ end end self end def succ Foo.new(@digits).increment(@digits.length-1) end def <=>(other) @digits <=> other.digits end def to_s digits.join end def inspect to_s end end range = Foo.new([5,0,0])..Foo.new([5,9,9]) range.to_a #=> [500, 505, 506, 507, 508, 509, 550, 555, 556, 557, 558, 559, 560, 565, 566, 567, 568, 569, 570, 575, 577, 578, 579, 580, 585, 588, 589, 590, 595, 599] 

The basic rule for increasing numbers is:

 @digits[i] = @digits[0,i].sort.detect { |e| e >= succ } || succ 

This sorts the digits remaining before the current digit (those that are entered on the left) and detects the first element that is equal to or greater than the successor. If none of them are found, the successor is used.

Answer 2

If you need this as an executable:

 #!/usr/bin/env ruby -w def output(start, stop) (start..stop).select do |num| digits = num.to_s.split('').to_a digits.map! { |d| d.to_i } checks = [] while digit = digits.shift next if digit == 0 next if checks.find { |d| break true if digit == d } break false if checks.find { |d| break true if digit < d } checks << digit end != false end end p output(*$*[0..1].map { |a| a.to_i }) 

---

 $ ./test.rb 560 570 [560, 565, 566, 567, 568, 569, 570] 

Answer 3

Note: three solutions are shown; find cleavage.

Describe a real number, then (1..INFINITE).select{|n| valid(n)}.take(1) (1..INFINITE).select{|n| valid(n)}.take(1)

So what really is? Well, allow yourself to take advantage here:

 class Fixnum def to_a to_s.split('').collect{|d| d.to_i} end end 123.to_a == [1,2,3] 

So now: Each digit can be a digit already present or zero, or a digit larger than the previous value, and the first digit is always valid.

PS - I use i not i-1 because the loop index is less than set 's, since I disabled the first element.

 def valid num #Ignore zeros: set = num.to_a.select{|d| d != 0 } #First digit is always valid: set[1..-1].each_with_index{ |d, i| if d > set[i] # puts "Increasing digit" elsif set[0..i].include? d # puts "Repeat digit" else # puts "Digit does not pass" return false end } return true end 

So, cheers for the lazy:

  (1..Float::INFINITY).lazy.select{|n| valid n}.take(100).force #=> [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 22, 23, 24, # 25, 26, 27, 28, 29, 30, 33, 34, 35, 36, 37, 38, 39, 40, 44, 45, 46, 47, 48, 49, 50, 55, # 56, 57, 58, 59, 60, 66, 67, 68, 69, 70, 77, 78, 79, 80, 88, 89, 90, 99, 100, 101, 102, # 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 120, # 121, 122, 123, 124, 125, 126, 127, 128, 129, 130, 131, 133, 134, 135, 136] 

Now that we have this, make it concise:

 def valid2 num set = num.to_a.select{|d| d != 0 } set[1..-1].each_with_index{ |d, i| return false unless (d > set[i]) || (set[0..(i)].include? d) } return true end 

check:

 (1..Float::INFINITY).lazy.select{|n| valid n}.take(100).force - (1..Float::INFINITY).lazy.select{|n| valid2 n}.take(100).force #=> [] 

all together now:

 def valid num set = num.to_s.split('').collect{|d| d.to_i}.select{|d| d != 0 } set[1..-1].each_with_index{ |d, i| return false unless (d > set[i]) || (set[0..(i)].include? d) } return true end 

Edit: If you want a specific subset of the set, just change the range. Your original will look like this:

 (500..1000).select{|n| valid n} 

Edit2: To create a range for a given number of digits n :

 ((Array.new(n-1, 0).unshift(1).join('').to_i)..(Array.new(n, 0).unshift(1).join('').to_i)) 

---

Edit3: An interesting alternative method is to delete digits recursively when they become valid.

 def _rvalid set return true if set.size < 2 return false if set[1] < set[0] return _rvalid set.select{|d| d != set[0]} end def rvalid num return _rvalid num.to_s.split('').collect{|d| d.to_i}.select{|d| d != 0 } end (1..Float::INFINITY).lazy.select{|n| rvalid n}.take(100).force 

---

Edit 4: Positive Generation Method

 def _rgen set, target return set if set.size == target ((set.max..9).to_a + set.uniq).collect{ |d| _rgen((set + [d]), target) } end def rgen target sets = (0..9).collect{|d| _rgen [d], target } # This method has an array problem that I'm not going to figure out right now while sets.first.is_a? Array sets = sets.flatten end sets.each_slice(target).to_a.collect{|set| set.join('').to_i} end 

Answer 4

This is some C # / pseudo code. It will definitely not compile. The implementation is not linear, but I note that you can add simple optimizations to make them more efficient. The algorithm is quite simple, but it looks pretty reasonable (it is linear with respect to the output. I assume that the result grows exponentially ... so this algorithm is also exponential, but with a hard constant).

 // Note: I've never used BigInteger before. I don't even know what the // APIs are. Basically you can use strings but hopefully the arbitrary // precision arithmetic class/struct would be more efficient. You // mentioned that you intend to add more than just 10 digits. In // that case you pretty much have to use a string without rolling out // your own special class. Perhaps C# has an arbitrary precision arithmetic // which handles arbitrary base as well? // Note: We assume that possibleDigits is sorted in increasing order. But you // could easily sort. Also we assume that it doesn't contain 0. Again easy fix. public List<BigInteger> GenSequences(int numDigits, List<int> possibleDigits) { // We have special cases to get rid of things like 000050000... // hard to explain, but should be obvious if you look at it // carefully if (numDigits <= 0) { return new List<BigInteger>(); } // Starts with all of the valid 1 digit (except 0) var sequences = new Queue<BigInteger>(possibleDigits); // Special case if numDigits == 1 if (numDigits == 1) { sequences.Enqueue(new BigInteger(0)); return sequences; } // Now the general case. We have all valid sequences of length 1 // (except 0 because no valid sequence of length greater than 1 // will start with 0) for (int length = 1; length <= numDigits; length++) { // Naming is a bit weird. A 'sequence' is just a BigInteger var sequence = sequences.Dequeue(); while (sequence.Length == length) { // 0 always works var temp = sequence * 10; sequences.Enqueue(temp); // Now do all of the other possible last digits var largestDigitIndex = FindLargestDigitIndex(sequence, possibleDigits); for (int lastDigitIndex = largestDigitIndex; lastDigitIndex < possibleDigits.Length; lastDigitIndex++) { temp = sequence * 10 + possibleDigits[lastDigitIndex]; sequences.Enqueue(temp); } sequence = sequences.Dequeue(); } } } // TODO: This is the slow part of the algorithm. Instead, keep track of // the max digit of a given sequence Meaning 5705 => 7. Keep a 1-to-1 // mapping from sequences to largestDigitsInSequences. That linear // overhead in memory and reduces time complexity to linear _with respect to the // output_. So if the output is like `O(k^n)` where `k` is the number of possible // digits and `n` is the number of digits in the output sequences, then it's // exponential private int FindLargestDigitIndex(BigInteger number, List<int> possibleDigits) { // Just iterate over the digits of number and find the maximum // digit. Then return the index of that digit in the // possibleDigits list } 

I prove why the algorithm works in the comments above (mostly, at least). This is an inductive argument. For a general n > 1 you can take any possible sequence. The first digits of n-1 (starting from the left) should form a sequence that is also valid (from the contrary). Using induction and then checking the logic in the innermost loop, we see that our desired sequence will be output. In this particular implementation, you will need some evidence of termination, etc. For example, the point of Queue is that we want to process sequences of length n , while we add sequences of length n+1 to the same Queue . Queue ordering allows you to complete the innermost while (because we will go through all sequences of length n before we get sequences n+1 ).

Answer 5

It does not seem too complicated. Write a refinement of the base N increment, with a change that, when a digit increases from zero, goes directly to the largest of the digits to the left of it.

Update . I read the specification incorrectly and my down payment was not fulfilled. Depending on the actual dataset, uniq.sort may be too expensive, but it is ok if the elements in the sequence have only a few digits. The correct way would be to save a second, sorted copy of the numbers, but I leave it that way until I know that it is too inefficient.

Note that the values ​​0..N here are intended to be used as indices in a sorted list of actual values ​​that each digit can take. A map call will generate valid sequence elements.

This program unloads the same section of the sequence as you do (it all starts with five).

 def inc!(seq, limit) (seq.length-1).downto(0) do |i| if seq[i] == limit seq[i] = 0 else valid = seq.first(i).uniq.sort valid += ((valid.last || 0).next .. limit).to_a seq[i] = valid.find { |v| v > seq[i] } break end end end seq = Array.new(3,0) loop do puts seq.join if seq[0] == 5 inc!(seq, 9) break if seq == [0,0,0] end 

Output

 500 505 506 507 508 509 550 555 556 557 558 559 560 565 566 567 568 569 570 575 577 578 579 580 585 588 589 590 595 599