我認爲,我的解決方法是比別人
def withReplacements(chars: String, n: Int) {
def internal(path: String, acc: List[String]): List[String] = {
if (path.length == n) path :: acc else
chars.toList.flatMap {c => internal(path + c, acc)}
}
val res = internal("", Nil)
println("there are " + res.length + " " + n + "-permutations with replacement for " + chars + " = " + res)
} //> withReplacements: (chars: String, n: Int)Unit
def noReplacements(chars: String, n: Int) {
//val set = chars.groupBy(c => c).map {case (c, list) => (c -> list.length)}.toList
import scala.collection.immutable.Queue
type Set = Queue[Char]
val set = Queue[Char](chars.toList: _*)
type Result = Queue[String]
// The idea is that recursions will scan the set with one element excluded.
// Queue was chosen to implement the set to enable excluded element to bubble through it.
def internal(set: Set, path: String, acc: Result): Result = {
if (path.length == n) acc.enqueue(path)
else
set.foldLeft(acc, set.dequeue){case ((acc, (consumed_el, q)), e) =>
(internal(q, consumed_el + path, acc), q.enqueue(consumed_el).dequeue)
}. _1
}
val res = internal(set, "", Queue.empty)
println("there are " + res.length + " " + n + "-permutations without replacement for " + set + " = " + res)
} //> noReplacements: (chars: String, n: Int)Unit
withReplacements("abc", 2) //> there are 9 2-permutations with replacement for abc = List(aa, ab, ac, ba,
//| bb, bc, ca, cb, cc)
noReplacements("abc", 2) //> there are 6 2-permutations without replacement for Queue(a, b, c) = Queue(b
//| a, ca, cb, ab, ac, bc)
noReplacements("abc", 3) //> there are 6 3-permutations without replacement for Queue(a, b, c) = Queue(c
//| ba, bca, acb, cab, bac, abc)
withReplacements("abc", 3) //> there are 27 3-permutations with replacement for abc = List(aaa, aab, aac,
//| aba, abb, abc, aca, acb, acc, baa, bab, bac, bba, bbb, bbc, bca, bcb, bcc,
//| caa, cab, cac, cba, cbb, cbc, cca, ccb, ccc)
// you can run with replacements (3 chars, n = 4) but noReplacements will fail for obvious reason -- you cannont combine 3 chars to produce 4
withReplacements("abc", 4) //> there are 81 4-permutations with replacement for abc = List(aaaa, aaab, aaa
//| c, aaba, aabb, aabc, aaca, aacb, aacc, abaa, abab, abac, abba, abbb, abbc,
//| abca, abcb, abcc, acaa, acab, acac, acba, acbb, acbc, acca, accb, accc, baa
//| a, baab, baac, baba, babb, babc, baca, bacb, bacc, bbaa, bbab, bbac, bbba,
//| bbbb, bbbc, bbca, bbcb, bbcc, bcaa, bcab, bcac, bcba, bcbb, bcbc, bcca, bcc
//| b, bccc, caaa, caab, caac, caba, cabb, cabc, caca, cacb, cacc, cbaa, cbab,
//| cbac, cbba, cbbb, cbbc, cbca, cbcb, cbcc, ccaa, ccab, ccac, ccba, ccbb, ccb
//| c, ccca, cccb, cccc)
(1 to 3) foreach (u => noReplacements("aab", u))//> there are 3 1-permutations without replacement for Queue(a, a, b) = Queue(a
//| , a, b)
//| there are 6 2-permutations without replacement for Queue(a, a, b) = Queue(a
//| a, ba, ba, aa, ab, ab)
//| there are 6 3-permutations without replacement for Queue(a, a, b) = Queue(b
//| aa, aba, aba, baa, aab, aab)
這些是相同的3行代碼,但可變長度排列,支持和列表級聯被淘汰更好。
我已經提出了更多的意識形態(這樣可以防止累加器的平面圖合併,這也使得它更具尾部遞歸性)並且擴展爲多重集合排列,以便您可以說「aab」,「aba 「和」咩「是相互排列的。這個想法是,字母「a」可以無限次(可替換的情況下)可替換兩次或僅可用一次(無替換)。所以,你需要一個計數器,它告訴你每個字母有多少次可供替換。
// Rewrite with replacement a bit to eliminate flat-map merges.
def norep2(chars: String, n: Int/* = chars.length*/) {
import scala.collection.immutable.Queue
type Set = Queue[Char]
val set = Queue[Char](chars.toList: _*)
type Result = Queue[String]
def siblings(set: (Char, Set), offset: Int, path: String, acc: Result): Result = set match {case (bubble, queue) =>
val children = descend(queue, path + bubble, acc) // bubble was used, it is not available for children that will produce combinations in other positions
if (offset == 0) children else siblings(queue.enqueue(bubble).dequeue, offset - 1, path, children) // siblings will produce different chars at the same position, fetch next char for them
}
def descend(set: Set, path: String, acc: Result): Result = {
if (path.length == n) acc.enqueue(path) else siblings(set.dequeue, set.size-1, path, acc)
}
val res = descend(set, "", Queue.empty)
println("there are " + res.length + " " + n + "-permutations without replacement for " + set + " = " + res)
} //> norep2: (chars: String, n: Int)Unit
assert(norep2("abc", 2) == noReplacements("abc", 2))
//> there are 6 2-permutations without replacement for Queue(a, b, c) = Queue(a
//| b, ac, bc, ba, ca, cb)
//| there are 6 2-permutations without replacement for Queue(a, b, c) = Queue(b
//| a, ca, cb, ab, ac, bc)
assert(norep2("abc", 3) == noReplacements("abc", 3))
//> there are 6 3-permutations without replacement for Queue(a, b, c) = Queue(a
//| bc, acb, bca, bac, cab, cba)
//| there are 6 3-permutations without replacement for Queue(a, b, c) = Queue(c
//| ba, bca, acb, cab, bac, abc)
def multisets(chars: String, n: Int/* = chars.length*/) {
import scala.collection.immutable.Queue
type Set = Queue[Bubble]
type Bubble = (Char, Int)
type Result = Queue[String]
def siblings(set: (Bubble, Set), offset: Int, path: String, acc: Result): Result = set match {case ((char, avail), queue) =>
val children = descend(if (avail - 1 == 0) queue else queue.enqueue(char -> {avail-1}), path + char, acc) // childern can reuse the symbol while if it is available
if (offset == 0) children else siblings(queue.enqueue((char, avail)).dequeue, offset - 1, path, children)
}
def descend(set: Set, path: String, acc: Result): Result = {
if (path.length == n) acc.enqueue(path) else siblings(set.dequeue, set.size-1, path, acc)
}
val set = Queue[Bubble]((chars.toList groupBy (c => c) map {case (k, v) => (k, v.length)}).toList: _*)
val res = descend(set, "", Queue.empty)
println("there are " + res.length + " multiset " + n + "-permutations for " + set + " = " + res)
} //> multisets: (chars: String, n: Int)Unit
assert(multisets("abc", 2) == norep2("abc", 2)) //> there are 6 multiset 2-permutations for Queue((b,1), (a,1), (c,1)) = Queue(
//| ba, bc, ac, ab, cb, ca)
//| there are 6 2-permutations without replacement for Queue(a, b, c) = Queue(a
//| b, ac, bc, ba, ca, cb)
assert(multisets("abc", 3) == norep2("abc", 3)) //> there are 6 multiset 3-permutations for Queue((b,1), (a,1), (c,1)) = Queue(
//| bac, bca, acb, abc, cba, cab)
//| there are 6 3-permutations without replacement for Queue(a, b, c) = Queue(a
//| bc, acb, bca, bac, cab, cba)
assert (multisets("aaab", 2) == multisets2("aaab".toList, 2))
//> there are 3 multiset 2-permutations for Queue((b,1), (a,3)) = Queue(ba, ab,
//| aa)
//| there are 3 multiset 2-permutations for Queue((b,1), (a,3)) = List(List(a,
//| a), List(b, a), List(a, b))
multisets("aab", 2) //> there are 3 multiset 2-permutations for Queue((b,1), (a,2)) = Queue(ba, ab,
//| aa)
multisets("aab", 3) //> there are 3 multiset 3-permutations for Queue((b,1), (a,2)) = Queue(baa, ab
//| a, aab)
norep2("aab", 3) //> there are 6 3-permutations without replacement for Queue(a, a, b) = Queue(a
//| ab, aba, aba, aab, baa, baa)
由於generalizaiton,你可以用/獲取,而無需使用多集功能可按替代品。例如,
//take far more letters than resulting permutation length to emulate withReplacements
assert(multisets("aaaaabbbbbccccc", 3) == withReplacements("abc", 3))
//> there are 27 multiset 3-permutations for Queue((b,5), (a,5), (c,5)) = Queue
//| (bac, bab, baa, bcb, bca, bcc, bba, bbc, bbb, acb, aca, acc, aba, abc, abb,
//| aac, aab, aaa, cba, cbc, cbb, cac, cab, caa, ccb, cca, ccc)
//| there are 27 3-permutations with replacement for abc = List(aaa, aab, aac,
//| aba, abb, abc, aca, acb, acc, baa, bab, bac, bba, bbb, bbc, bca, bcb, bcc,
//| caa, cab, cac, cba, cbb, cbc, cca, ccb, ccc)
//take one letter of each to emulate withoutReplacements
assert(multisets("aaaaabbbbbccccc", 3) == noReplacements("abc", 3))
//> there are 27 multiset 3-permutations for Queue((b,5), (a,5), (c,5)) = Queue
//| (bac, bab, baa, bcb, bca, bcc, bba, bbc, bbb, acb, aca, acc, aba, abc, abb,
//| aac, aab, aaa, cba, cbc, cbb, cac, cab, caa, ccb, cca, ccc)
//| there are 6 3-permutations without replacement for Queue(a, b, c) = Queue(c
//| ba, bca, acb, cab, bac, abc)
If you are more interested about permutations, you may look at
這也許應該是codereview.SE。 – Raphael
@Raphael我不得不穀歌那一個,所以這裏是懶惰http://codereview.stackexchange.com/ – simbo1905
我認爲OP是好的SO。人們需要了解其他人可能會如何處理某些問題,在這裏進行排列,以改進Scala編程。 – lcn