ruby - 条件下所有可能的排列

Question

我想知道 Ruby 中是否有一种优雅的方法来提出一些整数的所有排列(重复)，要求 1) 引入的整数必须按从左到右的升序排列 2) 零除外从这个规则。

在下面，我有一个三位数和整数 0、1、2、3、4、5、6、7、8、9 的输出子集。这只是总答案的一个子集，特别是它以 5 开头的子集。我已经包含了其中几个的注释

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

我需要能够针对任意长的输出长度(不只是 3，如本例)执行此操作，并且我需要能够针对特定的整数集执行此操作。但是，零始终是排序规则不适用的整数。

Answer 1

这会起作用:

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]

递增数字的主要规则是:

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

这会将当前数字左边的数字(“引入到左侧”的数字)排序，并检测等于或大于后继数字的第一个元素。如果没有找到，则使用后继者本身。