-1

我是 ruby​​ 新手，正在解决这样的问题：

有 n 个编号的字母和 n 个编号的信封。字母 x 不能放入信封 x 中。（OP 只想要索引 x-1 处没有 x 值的值）我想要的是打印出所有可能的情况。

Array + 1的索引--->信封号

Array的元素--->字母的个数

Input: n = 3.

Output: [2, 3, 1], [3, 1, 2]

Input: n = 4.

Output:   [2, 1, 4, 3], [2, 3, 4, 1], [2, 4, 1, 3], [3, 1, 4, 2],
          [3, 4, 1, 2], [3, 4, 2, 1], [4, 1, 2, 3], [4, 3, 1, 2],
          [4, 3, 2, 1]

这是我的代码：

$nums = []
def f( already, n, times )
  if n > times
    $nums << already.dup
    return
  else
    1.upto(times) do |i|
      next if ((already.include? i) || n == i)
      already << i
      f( already, n+1, times )
      already.pop
    end
  end
end

我正在寻找更优雅的解决方案。

4

1 回答 1

2

使用permutation枚举器，拒绝所有与索引值x-1匹配的枚举器x：

def f(n, x)
  (1..n).to_a.permutation.reject{|p| p[x-1] == x}
end

> f 3, 3
  => [[1, 3, 2], [2, 3, 1], [3, 1, 2], [3, 2, 1]] 
> f 4, 4
  => [[1, 2, 4, 3], [1, 3, 4, 2], [1, 4, 2, 3], [1, 4, 3, 2], [2, 1, 4, 3], [2, 3, 4, 1], [2, 4, 1, 3], [2, 4, 3, 1], [3, 1, 4, 2], [3, 2, 4, 1], [3, 4, 1, 2], [3, 4, 2, 1], [4, 1, 2, 3], [4, 1, 3, 2], [4, 2, 1, 3], [4, 2, 3, 1], [4, 3, 1, 2], [4, 3, 2, 1]]

更新

再次查看您的问题，不清楚您是否要使用特定的x，或者只是逻辑应该适用于x. 如果第二个猜测是您想要的，那么请改用它：

def f(n)
  (1..n).to_a.permutation.reject{|p| p.any?{|x| p[x-1] == x}}
end

> f 3
  => [[2, 3, 1], [3, 1, 2]] 
> f 4
  => [[2, 1, 4, 3], [2, 3, 4, 1], [2, 4, 1, 3], [3, 1, 4, 2], [3, 4, 1, 2], [3, 4, 2, 1], [4, 1, 2, 3], [4, 3, 1, 2], [4, 3, 2, 1]]
于 2013-04-12T15:17:49.250 回答