Kann ich alle Multimengen von bestimmten Größe effizienter finden?

Question

eine Reihe von möglichen Werten gegeben und eine Reihe von „Ziffern“, mag ich jedes einzigartig, ungeordnete Gruppierung von Werten zu finden. Zum Beispiel, sagen Sie ein Alphabet von A, B, C. Alle Kombinationen von 3 Ziffern seien:

AAA
AAB
ABB
BBB
BBC
BCC
CCC
CCA
CAA
ABC

Das spezifische Problem zu lösen, ich versuche ein bisschen einfacher. Ich mache ein Blackjack-Spiel als eine Übung in F # ( ich habe über diese vor geschrieben). Die Art, wie ich bin Berechnung Hand Werte ist mit einer Liste von Listen von Karten mögliche Werte. Alle Karten mit Ausnahme der Ace haben ein einzelnes Element in der Liste, aber die Asse können entweder 1 oder 11. Die Umsetzung mit dem ich in diesem Beitrag kam viel Redundanz erzeugt. Zum Beispiel, 3 Asse würde eine Liste wie [3; 13; 13; 13; 23; 23; 23; 33] erstellen. Im Moment bin ich die endgültige Liste zu nehmen und es durch Distinct() läuft, aber es fühlt sich ein bisschen wie ein Hack.

diese alle zusammen binden, der Potentialwert Aces (1, 11) bildet, das Alphabet, und die Anzahl der Asse in der Hand bestimmt die Anzahl der Ziffern. In diesem Fall würde ich den Algorithmus will mit dem folgende Muster kommen:

1, 1 
1, 11
11,11

Etwas sagt ich Dynamische Programmierung hier ins Spiel kommen kann, aber mein Mangel an geeigneter Terminologie verlässt mir stecken ein bisschen. Jede mögliche Hilfe würde geschätzt.

Bearbeiten

Für das, was es wert ist, ich bin mir dessen bewusst, dass es viel einfacher Lösungen für das spezifische Problem, aber als eine Übung in der funktionalen Programmierung, Allgemeinheit ist eines meiner Ziele.

Answer 1

Dieses Problem ist ein gutes Gehirn Teaser. Es sollte Code Golf sein. :)

let rec permute list count =
    seq {
        match list with
        | y::ys when count > 0 -> 
            for n in permute list (count - 1) do
                yield Seq.map (fun li -> y::li) n
            yield Seq.concat (permute ys count)
        | y::ys -> yield Seq.singleton []
        | [] -> ()
    }

Ace Beispiel

permute ["1";"11"] 2
|> Seq.concat
|> Seq.iter (printfn "%A")

["1"; "1"]
["1"; "11"]
["11"; "11"]

ABC Beispiel

permute ["A";"B";"C"] 3
|> Seq.concat
|> Seq.iter (printfn "%A");;

["A"; "A"; "A"]
["A"; "A"; "B"]
["A"; "A"; "C"]
["A"; "B"; "B"]
["A"; "B"; "C"]
["A"; "C"; "C"]
["B"; "B"; "B"]
["B"; "B"; "C"]
["B"; "C"; "C"]
["C"; "C"; "C"]

y::li ist, wo alle concating Arbeit geschieht. Man könnte es mit y + li ersetzen, wenn alles, was Sie Strings wollte. Sie müssen auch eine yield Seq.singleton "" insted []

Performance Update:

Dieses Problem memoizes schön und viel bessere Leistung gibt für keine triviale Fälle memoized.

let memoize2 f = 
    let cache = Dictionary<_,_>()
    fun x y -> 
        let ok, res = cache.TryGetValue((x, y))
        if ok then 
            res 
        else 
            let res = f x y
            cache.[(x, y)] <- res
            res

// permute ["A";"B";"C"] 400 |> Seq.concat |> Seq.length |> printf "%A"       
// Real: 00:00:07.740, CPU: 00:00:08.234, GC gen0: 118, gen1: 114, gen2: 4
let rec permute =
    memoize2(fun list count ->
        seq {
            match list with
            | y::ys when count > 0 -> 
                for n in permute list (count - 1) do
                    yield Seq.map (fun li -> y::li) n |> Seq.cache
                yield Seq.concat (permute ys count)
            | y::ys -> yield Seq.singleton []
            | [] -> ()
        } |> Seq.cache)

ich auch memoized kvb Lösung und führt sie 15% schneller als meine.

// permute ["A";"B";"C"] 400 |> Seq.length |> printf "%A"
// Real: 00:00:06.587, CPU: 00:00:07.046, GC gen0: 87, gen1: 83, gen2: 4
let rec permute = 
    memoize2 (fun list n ->
        match n with
            | 0 -> Seq.singleton []
            | n -> 
                seq {
                    match list with 
                    | x::xs ->  
                        yield! permute list (n-1) |> Seq.map (fun l -> x::l)
                        yield! permute xs n
                    | [] -> () 
                } |> Seq.cache)

Answer 2

Hmm, in Ihrem Fall ist es genug, um (1) die Asse zählen (lassen Sie die Zählung sein N) und dann (2) erzeugen, den möglichen Gesamtwert als Liste Verständnis von

{ i * 11 + (N - i) * 1 }   |   0 <= i <= N }

... aber würden Sie, dass in F # auszudrücken. Keine Notwendigkeit tatsächliche Permutationen zu tun, Kombinatorik etc.

Answer 3

Hier ist eine semi-treue Übersetzung von Thomas Pornin Antwort auf F #. Beachten Sie, dass ich nicht erwarten, dass dies besonders performanter ist als der naive Ansatz distinct, aber es ist auf jeden Fall sauberer:

let rec splits l = function
| [] -> Seq.empty
| x::xs -> seq {
    yield [],x,xs
    for l,y,ys in splits xs do
      yield x::l,y,ys
  }

let rec combs s = function
| 0 -> Seq.singleton []
| n -> seq {
    for _,x,rest in splits s do
      for l in combs (x::rest) (n-1) do
        yield x::l
  }

Oder eine Variation gradbot-Lösung statt:

let rec permute list = function
| 0 -> Seq.singleton []
| n -> seq { 
    match list with 
    | x::xs ->  
        yield! permute list (n-1) |> Seq.map (fun l -> x::l)
        yield! permute xs n
    | [] -> () 
  }

Answer 4

Sie können es rekursiv tun. Ich schreibe dies in Java; mein F # ist nicht gut genug:

static void genCombInternal(int num, int[] base,
    int min, int max, Collection<int[]> dst)
{
    if (num == 0) {
        dst.add(base);
        return;
    }
    for (int i = min; i <= max; i ++) {
        int[] nb = new int[base.length + 1];
        System.arraycopy(base, 0, nb, 0, base.length);
        nb[base.length] = i;
        genCombInternal(num - 1, nb, i, max, dst);
    }
}

static Collection<int[]> genComb(int num, int min, int max)
{
    Collection<int[]> d = new ArrayList<int[]>();
    genCombInternal(num, new int[0], min, max, d);
    return d;
}

Dieser Code völlig ungetestet. Wenn es funktioniert, dann rufen genComb(num, min, max) soll alle Ihre „Kombinationen“ von num ganzen Zahlen im Bereich min zu max erzeugen (einschließlich), so dass keine zwei zurück Kombinationen speichern für die Bestellung gleich sind.

Das ist sehr nah an den Code, die „true“ Kombinationen erzeugt. Der Trick ist, in den erlaubten Zahlen bei jedem Schritt. Wenn Sie i in i+1 in dem rekursiven Aufruf ändern, dann sollten Sie die mathematischen Kombinationen bekommen

Answer 5

Bei Ihrem "Alphabet" von {1,11}, dann im Grunde Sie alle "Wörter" mit einer Länge von generieren möchten n , wobei n ist die Anzahl der Asse ist, so dass alle der 1'en (0 oder mehr) sind auf der linken Seite und alle der 11 sind die auf der rechten Seite. Die Reihenfolge spielt keine Rolle, das ist nur ein einfacher Ansatz, um eine Iteration durch die Kombinationen, die Ihnen wichtig sind.

In Python:

n = 3 # number of aces
hands = []
for i in range(0,n+1):
    hands.append([1] * (n-i) + [11] * i)

Oder noch einfacher in Python:

hands = [[1]*(n-i) + [11]*i for i in range(0,n+1)]

Um die Gesamtpunktzahl pro Hand zu bekommen:

scores = [sum(hand) for hand in hands]

Ein Hinweis auf Python-Syntax, wenn Sie nicht vertraut sind, Klammern [] bezeichnet eine Liste und [1]*x Mittel eine neue Liste erstellen, die die Verkettung von x Kopien von [1] ist; das heißt,

[1] * x ==  [1,1,1] 

Wenn x = 3