具有唯一數字的所有N位數長整數列表

Question

我試圖構造具有唯一數字的所有N位數長整數列表， 但我無法弄清楚如何推廣它，作爲較大的一部分問題，爲此我需要具有唯一數字的所有（1到N）數字長號的列表。

這裏是n的手寫代碼= 4：

for { 
    x1 <- 1 to 9 
    x2 <- 1 to 9 
    x3 <- 1 to 9 
    x4 <- 1 to 9 
    if (x1 != x2 && x2 != x3 && x3 != x4 && x1 != x3 && x1 != x4 && x2 != x4) 
    num4 = x1 + x2 * 10 + x3 * 100 + x4 * 1000 
} yield num4 

Answer 1

我的方法是過濾掉你不感興趣的結果
Filtering使用設置的財產，他們只。有不同的價值。
n> 10的情況與n = 10的情況不會產生不同的結果，所以我們可以默認回到那個。

def generateUniqueList(n: Int) = { 
    val sanitizedInput = if(n>10) 10 else n 
    0 to math.pow(10, sanitizedInput).toInt-1 filter(num => num.toString.toSeq.size == num.toString.toSet.size) 
} 

這不會產生最快的解決方案，但其概念簡單易懂。

例子：

val result = generateUniqueList(2) 
//> result : scala.collection.immutable.IndexedSeq[Int] = Vector(0, 1, 2, 3, 4, 
//| 5, 6, 7, 8, 9, 10, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 23, 24, 25, 26, 
//| 27, 28, 29, 30, 31, 32, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 45, 46, 47, 
//| 48, 49, 50, 51, 52, 53, 54, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 67, 68, 
//| 69, 70, 71, 72, 73, 74, 75, 76, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 89, 
//| 90, 91, 92, 93, 94, 95, 96, 97, 98) 

Answer 2

scala> "1234".combinations(2).toList 
res9: List[String] = List(12, 13, 14, 23, 24, 34) 

隨着範圍：

scala> (1 to 9).combinations(4).toList 
res12: List[scala.collection.immutable.IndexedSeq[Int]] = List(Vector(1, 2, 3, 4), Vector(1, 2, 3, 5), Vector(1, 2, 3, 6), Vector(1, 2, 3, 7), Vector(1, 2, 3, 8), Vector(1, 2, 3, 9), Vector(1, 2, 4, 5), Vector(1, 2, 4, 6), Vector(1, 2, 4, 7), Vector(1, 2, 4, 8), Vector(1, 2, 4, 9), Vector(1, 2, 5, 6), Vector(1, 2, 5, 7), Vector(1, 2, 5, 8), Vector(1, 2, 5, 9), Vector(1, 2, 6, 7), Vector(1, 2, 6, 8), Vector(1, 2, 6, 9), Vector(1, 2, 7, 8), Vector(1, 2, 7, 9), Vector(1, 2, 8, 9), Vector(1, 3, 4, 5), Vector(1, 3, 4, 6), Vector(1, 3, 4, 7), Vector(1, 3, 4, 8), Vector(1, 3, 4, 9), Vector(1, 3, 5, 6), Vector(1, 3, 5, 7), Vector(1, 3, 5, 8), Vector(1, 3, 5, 9), Vector(1, 3, 6, 7), Vector(1, 3, 6, 8), Vector(1, 3, 6, 9), Vector(1, 3, 7, 8), Vector(1, 3, 7, 9), Vector(1, 3, 8, 9), Vector(1, 4, 5... 

爲int的列表：

"123456789".combinations(4).map(_.toInt).toList 
res37: List[Int] = List(1234, 1235, 1236, 1237, 1238, 1239, 1245, 1246, 1247, 1248, 1249, 1256, 1257, 1258, 1259, 1267, 1268, 1269, 1278, 1279, 1289, 1345, 1346, 1347, 1348, 1349, 1356, 1357, 1358, 1359, 1367, 1368, 1369, 1378, 1379, 1389, 1456, 1457, 1458, 1459, 1467, 1468, 1469, 1478, 1479, 1489, 1567, 1568, 1569, 1578, 1579, 1589, 1678, 1679, 1689, 1789, 2345, 2346, 2347, 2348, 2349, 2356, 2357, 2358, 2359, 2367, 2368, 2369, 2378, 2379, 2389, 2456, 2457, 2458, 2459, 2467, 2468, 2469, 2478, 2479, 2489, 2567, 2568, 2569, 2578, 2579, 2589, 2678, 2679, 2689, 2789, 3456, 3457, 3458, 3459, 3467, 3468, 3469, 3478, 3479, 3489, 3567, 3568, 3569, 3578, 3579, 3589, 3678, 3679, 3689, 3789, 4567, 4568, 4569, 4578, 4579, 4589, 4678, 4679, 4689, 4789, 5678, 5679, 5689, 5789, 6789) 

如果你實際上感興趣的各種排列（問題已經改變了一點因爲我寫了上面的答案）

scala> "1234".combinations(2).toList.flatMap(_.permutations).map(_.toInt) 
res51: List[Int] = List(12, 21, 13, 31, 14, 41, 23, 32, 24, 42, 34, 43) 

Answer 3

你正在尋找被稱爲單子排序什麼。當使用for理解如

for(x <- Set(...) 
    y <- Set(...)) 
    yield (x, y) 

可以查看它具有一對一元計算(Set(...), Set(...))的並將其轉換成一個單子保持一對結果Set((...,...), (...,...), ...)的。

這可以概括爲任意長度的序列。該庫定義特徵Traversable，其表示我們可以定義這種操作的序列。這是traverse操作是更普遍的，我們可以用它來定義一元排序：

import scalaz._ 
import scalaz.Scalaz._ 
import scala.collection.immutable._ 

def sequence[M[_]: Applicative, T[_], A](seq: T[M[A]]) 
     (implicit t: Traverse[T]): M[T[A]] = 
    t.traverse(identity[M[A]], seq); 

在我們的情況下，M將Set和T將Seq。因此，考慮的選擇序列Seq[Set[Int]]類型（表示爲套），sequence將得到我們Set[Seq[Int]]這是所有可能的組合，從選擇採摘：

// a helper function 
def set[A](seq: Seq[A]): Set[A] = Set(seq : _*); 

// prints all sequences where the first number is from 1 to 9 
// and the second number from 2 to 9: 
println(sequence(List(set(1 to 9), set(2 to 9)))) 

---

然後，您可以過濾序列，其中某些數字會多次出現。

如果你想在這個過程中包含這種過濾，它會變得更加複雜。你需要在單計算過程中保持一些狀態，這將保持可用的數字。讓我們來定義

type Choices = Set[Int] 
type DigitChoose[A] = StateT[Set,Choices,A] 

所以DigitChoose是具有不確定性的結果（每一個操作產生一組可能出現的結果，像以前一樣），而且還使Choices型狀態的單子，它告訴我們的數字是什麼仍可用。接下來，我們定義一些幫助函數來幫助編譯器稍微（一般類型對它太多:)）。

// See http://stackoverflow.com/q/7782589/1333025 why we need this: 
implicit val applicativeDC: Applicative[DigitChoose] 
    = implicitly[Monad[DigitChoose]] 

def sequenceDC[A](seq: Seq[DigitChoose[A]]): DigitChoose[Seq[A]] 
    = sequence(seq); 

所以現在我們對於序列定義了DigitChoose的單子序列。

使用DigitChoose我們可以定義選擇一個位從可得的那些中的一個操作，並更新狀態（刪除從該組中的選擇的數字）：

// Pick any of the available digits: 
def choose: DigitChoose[Int] = 
    stateT((s: Choices) => for(i <- s) yield (s - i, i)); 

和一些限制變體限制的數字的選擇：

// Pick an available digit that is also in the given set of choices: 
def choose(c: Choices): DigitChoose[Int] = 
    stateT((s: Choices) => for(i <- s intersect c) yield (s - i, i)); 
// Pick an available digit that is also in the given set of choices: 
def choose(cs: Seq[Int]): DigitChoose[Int] 
    = choose(cs.toSet); 

最後，我們做這樣的事情：

// First digit is unrestricted 
// Second digit is from 1 to 3 
// Third digit is from 1 to 2 
// ... and no digits will be the same! 
val choices = Seq(choose, choose(1 to 3), choose(1 to 2)); 
// Sequence the choices, given that we start with digits 1 to 9 
println(sequenceDC(choices) ! Set(1 to 9 : _*)); 

The complete code is available on gist。