Я думаю, что мое решение лучше, чем другие
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" и "baa" - перестановки (друг друга). Идея состоит в том, что буква «а» заменяется два раза вместо бесконечно (с заменой) или доступна только один раз (без замены). Итак, вам нужен счетчик, который сообщает вам, сколько раз каждое письмо доступно для замены.
// 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)
Как обобщение, вы можете получить с / без замен, используя функцию мультимножества. Например,
//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)
Если вас больше интересует перестановка, вы можете посмотреть на