Note: Three solutions are shown; look for the splits.
Describe a valid number, then (1..INFINITE).select{|n| valid(n)}.take(1)
So what's valid? Well, let's take some advantage here:
class Fixnum
def to_a
to_s.split('').collect{|d| d.to_i}
end
end
123.to_a == [1,2,3]
Alright, so, now: Each digit can be a digit already present or zero, or a digit greater than the prior value, and the first digit is always valid.
PS - I use i
not i-1
because the loop's index is one less than set
's, since I lopped the first element off.
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 then, hurrah for 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 it, let's make it succinct:
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 particular subset of the set, just change the range. Your original would be:
(500..1000).select{|n| valid n}
Edit2: To generate the 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: Interesting alternative method - recursively remove digits as 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
n
has a valid "permutation" of lengthn-1
. Basically, you can't make a "bad" permutation into a "good" by adding another digit (this is true by contradiction). So an easy solution (not elegant yet) is to first deal with permutations with0
. Then separately compute alln-1
permutations recursively. Filling in the last digit is easy, but not performant... it's a start. – rliu Jun 15 '13 at 6:26