Могу ли я найти все мультимножества заданного размера более эффективно?

Question

Учитывая набор возможных значений и количество «цифр», я хочу найти каждую уникальную неупорядоченную группу значений. Например, скажем, у вас есть алфавит A, B, C. Все комбинации из 3 цифр будут:

AAA
AAB
ABB
BBB
BBC
BCC
CCC
CCA
CAA
ABC

Конкретная проблема, которую я пытаюсь решить, немного проще. Я играю в Блэкджек в качестве упражнения на F # ( Я уже писал об этом раньше ). Я рассчитываю значения рук с помощью списка возможных значений карт. У всех карт, кроме туза, есть один элемент в списке, но тузы могут быть либо 1, либо 11. Реализация, о которой я говорил в этом посте, создает много избыточности. Например, 3 туза создали бы список вроде [3; 13; 13; 13; 23; 23; 23; 33]. Прямо сейчас я беру окончательный список и проверяю его через Distinct(), но это похоже на хак.

Связывая все это вместе, потенциальные значения тузов (1, 11) составляют алфавит, а число тузов в руке определяет количество цифр. В этом случае я бы хотел, чтобы алгоритм придумал следующий шаблон:

1, 1 
1, 11
11,11

Что-то подсказывает мне Динамическое программирование может вступить в игру, но мое отсутствие соответствующей терминологии оставляет меня в тупике. Любая помощь будет оценена.

Редактировать

Что бы это ни стоило, я знаю, что есть гораздо более простые решения конкретной проблемы, но, будучи упражнением в функциональном программировании, обобщение является одной из моих целей.

Answer 1

Хм, в вашем случае достаточно (1) подсчитать тузов (пусть счет будет N), а затем (2) сгенерировать возможное общее значение в виде списка

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

... однако вы бы выразили это в F #. Нет необходимости делать реальные перестановки, комбинаторику и т. Д.

Answer 2

Эта проблема - хорошая головоломка. Это должен быть код гольф. :)

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 Пример

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

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

Пример ABC

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 - это место, где происходит вся конкрирующая работа. Вы можете заменить его на y + li, если вам нужны только строки. Вы также должны yield Seq.singleton и "" вместо []

Обновление производительности:

Эта проблема хорошо запоминается и дает гораздо лучшую производительность, запоминаемую ни для каких тривиальных случаев.

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)

Я также запомнил решение kvb, и оно работает на 15% быстрее, чем мое.

// 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 3

Вот полу-точный перевод ответа Томаса Порнина на F #. Обратите внимание, что я не ожидаю, что это будет более продуктивно, чем наивный подход с использованием distinct, но он определенно аккуратнее:

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
  }

Или вариант решения gradbot:

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

Если ваш «алфавит» равен {1,11}, то вы в основном хотите сгенерировать все «слова» длиной n , где n - количество тузов, например что все 1 (0 или более) слева и все 11 справа. Порядок не имеет значения, это просто простой способ перебирать комбинации, которые вас интересуют.

В Python:

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

Или еще проще в Python:

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

Чтобы получить общий счет за раздачу:

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

Примечание о синтаксисе Python, если вы незнакомы, скобки [] обозначают список, а [1]*x означает создание нового списка, представляющего собой объединение x копий [1]; то есть

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

если x = 3

Answer 5

Вы можете сделать это рекурсивно. Я пишу это на Java; мой F # недостаточно хорош:

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;
}

Этот код полностью не проверен. Если это работает, то вызов genComb(num, min, max) должен сгенерировать все ваши "комбинации" из num целых чисел в диапазоне от min до max (включительно), так что никакие две возвращенные комбинации не будут равны, за исключением порядка.

Это очень близко к коду, который генерирует "истинные" комбинации. Хитрость заключается в допустимых целых числах на каждом шаге: если вы измените i на i+1 в рекурсивном вызове, то вы должны получить математические комбинации.