Sort shuffle

Question

我問了關於Number shuffle https://rubymonk.com/learning/books/1-ruby-primer/problems/154-permutations問題並收到了滿意的答案，但是這個練習對我來說還不完全清楚。練習題要求：

給定一個3位或4位數字以不同的數字，返回一個所有可以用這些數字構成的唯一數字的排序數組。

例子：

考慮：123

返回：[123, 132, 213, 231, 312, 321]

有鍛鍊低於溶液（見解決方案），看起來像這樣：

def number_shuffle(number) 
    no_of_combinations = number.to_s.size == 3 ? 6 : 24 
    digits = number.to_s.split(//) 
    combinations = [] 
    combinations << digits.shuffle.join.to_i while combinations.uniq.size!=no_of_combinations 
    combinations.uniq.sort 
end 

我有2個問題stions，任何人都可以給我解釋一下：

1. no_of_combinations變量i解釋這樣：如果number.to_s.size等於3個位數，那麼組合的數量應該是6，否則24 am我正確與否？

2. 這是什麼意思：combinations.uniq.size!=no_of_combinations。我知道運營商!=指定「不等於」，但不明白總體意義。

Answer 1

1. ...如果number.to_s.size等於3個位數，那麼組合的數量應該是6，否則24 am我正確與否？

正確的，因爲有6種方法來安排3位和24點的方式，安排4位。

1. 這是什麼意思：combinations.uniq.size!=no_of_combinations。

while之前的部分被重複，直到該方程被滿足，即一個隨機組合被創建：

digits = [1, 2 ,3] 
digits.shuffle.join.to_i #=> 123 
digits.shuffle.join.to_i #=> 132 
digits.shuffle.join.to_i #=> 321 
digits.shuffle.join.to_i #=> 123 

...，直到該數組包含這種組合被添加到陣列combinationsno_of_combinations獨特的元素。

當然，這遠非理想，因爲可以一次又一次創建相同的組合。

Answer 2

你能做到在同一行：

def number_shuffle(i) 
    i.to_s.chars.permutation.map(&:join).map(&:to_i) 
end 

輸出：

number_shuffle(123) 
# => [123, 132, 213, 231, 312, 321] 

number_shuffle(1234) 
# => [1234, 1243, 1324, 1342, 1423, 1432, 2134, 2143, 2314, 2341, 2413, 2431, 3124, 3142, 3214, 3241, 3412, 3421, 4123, 4132, 4213, 4231, 4312, 4321] 

在這個問題的解決方案是錯誤和低效。它會生成隨機排列，直到找到適當的唯一組合數。這就像通過替換隨機值求解方程：

# x - 5 should be 0. Let's find x! 
x = rand() unless x - 5 == 0 

不要那樣做。

Answer 3

關於第一個問題：

鑑於的具有不同位的號碼的數字排列的數量是n!（1 * 2 * ... * n）。

如果數字有3個數字那麼置換的數量爲3! = 1 * 2 * 3 = 6

如果數字有4個數字，然後置換的數量是4! = 1 * 2 * 3 * 4 = 24

因此，在這種特殊情況下，你是對的。請注意，如果您的數字在該數字中重複，則這不起作用。

關於第二個問題：

combinations.uniq.size!=no_of_combinations是一個布爾測試，它返回true或false。結合while聲明：some_code while boolean_test，這意味着執行代碼some_code而boolean_test爲真。

在你的情況：

combinations << digits.shuffle.join.to_i while 
combinations.uniq.size!=no_of_combinations 

指：

推digits.shuffle.join.to_i到可變combinations（這是一個數組） 而combinations.uniq.size!=no_of_combinations是真，也就是說，可以在陣列的大小（combinations）是小於預期長度（這是之前計算的）。

這裏的算法首先確定預期的解決方案的數量（6或24），然後它挑選一個隨機的數字混洗，如果它不存在，則將其添加到解決方案中，並且只在解決方案的數量嚴格時停止等於預期的解決方案數量。

這顯然不是最好的解決方案（請參閱@ Oleg K.答案），但是我猜這裏的目標是告訴你Array#shuffle是如何工作的。

Answer 4

Q1

你不需要被告知。想辦法。假設p(n)是您可以安排（「置換」）具有不同數字的數字的數字的方式的數量。首先，假設n=1。那麼很明顯，

p(1) = 1 

現在假設n=2。第一個數字可以之前或之後的第二位，所以：

p(2) = 2*p(1) = 2 

現在讓n是任意整數比2更大。對於最後一個n-1數字的每個排列，第一個數字可以插入n的任意位置。例如，假設數字是1234。最後三位數字的一種排列是423。第一個數字1可插入4位置的任何一個：1423, 4123, 4213, 4231。

因此：

p(n) = n*p(n-1) 

看來：

p(n) = n! 

我們可以很容易地證明，通過感應是正確的：

p(1) = 1 
p(2) = 2*1 = 2! 
p(n) = n*p(n-1) 
    = n*(n-1)! 
    = n! 

所以：

p(3) = 3! = 6 
p(4) = 4! = 4*3! = 4*6 = 24 

現在你已經知道了這個公式，並知道爲什麼它是真的，你不會忘記它。

Q2

讓我們重寫方法與一些puts補充：

def number_shuffle(number) 
    no_of_combinations = number.to_s.size == 3 ? 6 : 24 
    puts "no_of_combinations = #{no_of_combinations}" 
    digits = number.to_s.split(//) 
    puts "digits = #{digits}\n\n" 
    combinations = [] 
    while true 
    a = digits.shuffle.join.to_i 
    puts "digits.shuffle.join.to_i = #{a}" 
    combinations << a 
    puts "combinations = #{combinations}" 
    b = combinations.uniq 
    puts " combinations.uniq = #{b}" 
    c = b.size 
    puts " combinations.uniq.size = #{c}" 
    puts " combinations.uniq.size==no_of_combos = #{c==no_of_combinations}" 
    break if c==no_of_combinations 
    end 
    combinations.uniq.sort 
end 

和嘗試：

number_shuffle(123) 

no_of_combinations = 6 
digits = ["1", "2", "3"] 

digits.shuffle.join.to_i = 123 
combinations = [123] 
    combinations.uniq = [123] 
    combinations.uniq.size = 1 
    combinations.uniq.size==no_of_combinations = false 

digits.shuffle.join.to_i = 321 
combinations = [123, 321] 
    combinations.uniq = [123, 321] 
    combinations.uniq.size = 2 
    combinations.uniq.size==no_of_combinations = false 

digits.shuffle.join.to_i = 123 
combinations = [123, 321, 123] 
    combinations.uniq = [123, 321] 
    combinations.uniq.size = 2 
    combinations.uniq.size==no_of_combinations = false 

digits.shuffle.join.to_i = 312 
combinations = [123, 321, 123, 312] 
    combinations.uniq = [123, 321, 312] 
    combinations.uniq.size = 3 
    combinations.uniq.size==no_of_combinations = false 

digits.shuffle.join.to_i = 321 
combinations = [123, 321, 123, 312, 321] 
    combinations.uniq = [123, 321, 312] 
    combinations.uniq.size = 3 
    combinations.uniq.size==no_of_combinations = false 

digits.shuffle.join.to_i = 132 
combinations = [123, 321, 123, 312, 321, 132] 
    combinations.uniq = [123, 321, 312, 132] 
    combinations.uniq.size = 4 
    combinations.uniq.size==no_of_combinations = false 

digits.shuffle.join.to_i = 321 
combinations = [123, 321, 123, 312, 321, 132, 321] 
    combinations.uniq = [123, 321, 312, 132] 
    combinations.uniq.size = 4 
    combinations.uniq.size==no_of_combinations = false 

digits.shuffle.join.to_i = 213 
combinations = [123, 321, 123, 312, 321, 132, 321, 213] 
    combinations.uniq = [123, 321, 312, 132, 213] 
    combinations.uniq.size = 5 
    combinations.uniq.size==no_of_combinations = false 

digits.shuffle.join.to_i = 213 
combinations = [123, 321, 123, 312, 321, 132, 321, 213, 213] 
    combinations.uniq = [123, 321, 312, 132, 213] 
    combinations.uniq.size = 5 
    combinations.uniq.size==no_of_combinations = false 

digits.shuffle.join.to_i = 123 
combinations = [123, 321, 123, 312, 321, 132, 321, 213, 213, 123] 
    combinations.uniq = [123, 321, 312, 132, 213] 
    combinations.uniq.size = 5 
    combinations.uniq.size==no_of_combinations = false 

digits.shuffle.join.to_i = 231 
combinations = [123, 321, 123, 312, 321, 132, 321, 213, 213, 123, 231] 
    combinations.uniq = [123, 321, 312, 132, 213, 231] 
    combinations.uniq.size = 6 
    combinations.uniq.size==no_of_combinations = true 

#=> [123, 132, 213, 231, 312, 321]