4

我想知道 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,就像这个例子),我需要能够为特定的整数集做到这一点。但是,零始终是排序规则不适用的整数。

4

5 回答 5

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

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

于 2013-06-15T11:13:15.553 回答
1

如果您需要它作为可执行文件:

#!/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]
于 2013-06-15T20:15:53.870 回答
0

注意:显示了三种解决方案;寻找分裂。

描述一个有效的数字,然后(1..INFINITE).select{|n| valid(n)}.take(1)

那么什么是有效的?好吧,让我们在这里利用一些优势:

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

好的,所以,现在:每个数字都可以是已经存在的数字或零,或大于先前值的数字,并且第一个数字始终有效。

PS - 我使用inoti-1因为循环的索引比set's 少一个,因为我删除了第一个元素。

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

那么,为懒惰而欢呼吧:

  (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]

现在我们有了它,让我们让它简洁:

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

查看:

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

现在都在一起了:

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

编辑:如果您想要该集合的特定子集,只需更改范围。您的原件将是:

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

Edit2:要生成给定位数的范围n

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

Edit3:有趣的替代方法 - 递归删除有效的数字。

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

编辑4:正生成方法

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
于 2013-06-15T08:09:31.803 回答
0

这似乎并不太复杂。写出一个以 N 为底的增量的改进,其变化是当一个数字从零递增时,它会直接移动到它左边的最大数字。

更新我误读了规范,我最初对此的看法并没有完全执行。根据实际的数据集,这uniq.sort可能成本太高,但是当序列中的项目只有几位数字时就可以了。正确的方法是维护第二个已排序的数字副本,但我会这样保留它,直到我知道它效率太低。

请注意,此处的 0..N 值旨在用作每个数字可以采用的实际值的排序列表中的索引。调用map将生成序列的真实元素。

该程序转储与您自己展示的序列相同的部分(所有内容都以 5 开头)。

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

输出

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
于 2013-06-15T17:14:33.777 回答
0

这是一些 C#/伪代码。它肯定不会编译。实现不是线性的,但我注意到你可以在哪里添加一个简单的优化来提高效率。该算法非常简单,但它的性能似乎相当合理(它相对于输出是线性的。我猜输出呈指数增长......所以这个算法也是指数的。但有一个紧密的常数)。

// 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's 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
}

我在上面的评论中证明了为什么该算法有效(至少大部分情况下)。这是一个归纳论证。一般来说n > 1,您可以采取任何可能的顺序。第一个n-1数字(从左开始)必须形成一个同样有效的序列(通过矛盾)。使用归纳法,然后检查最内层循环中的逻辑,我们可以看到我们想要的序列将被输出。这个特定的实现你还需要一些关于终止等的证明。例如, 的重点Queue是我们要在将长度n序列添加n+1相同 Queue的 时处理长度序列。的排序Queue允许最里面的while循环终止(因为我们将遍历所有长度的序列n在我们进入n+1序列之前)。

于 2013-06-15T08:49:20.693 回答