-1

私はルビーが初めてで、そのような問題に取り組んでいます:

n 個の番号付きの手紙と n 個の番号付きの封筒があります。文字 x をエンベロープ x に入れることはできません (OP は、インデックス x-1 に x の値がない値のみを必要とします) 私が望むのは、すべての可能なケースを出力することです。

配列のインデックス + 1 ---> エンベロープの番号

配列の要素 ---> 文字の番号

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-1x

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。2 番目の推測が必要な場合は、代わりにこれを使用します。

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 に答える