Алгоритм для генерации каждой комбинации из n элементов, разбитых на k множеств

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

То есть эти два решения идентичны: 

[a,b,c,d,e,f][g,h,i,j,k,l][m,n,o,p,q,r,s][t,u,v,w,x,y,z]
[f,b,c,d,e,a][l,h,i,j,k,g][s,n,o,p,q,r,m][z,u,v,w,x,y,t]

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

Существует ли именованный алгоритм, который может разбитьnk элементов на n наборов k элементов, генерируя каждую комбинацию эти декорации? Если нет, то мне придется самому что-нибудь придумать. Но это похоже на проблему, которая уже решена.

2 3
algorithm combinations

2 ответа:

Я не знаю никаких названий алгоритмов для этого (хотя один, вероятно, существует), но подход, который я упомянул в комментариях, избегает работы с дубликатами и настолько эффективен, насколько я могу себе представить.

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

Вот реализация C#. Он может генерировать 10 000 000 комбинаций менее чем за 30 секунд, и 2/3 этого времени тратится только на построение строковых выходов: 

void Main()
{
    // Tweak these starting values to create smaller subsets if you want.
    var letters = Enumerable.Range(0, 26).Select(i => (char)('a' + i)).ToList();
    var buckets = new[]{new Bucket(6), new Bucket(6), new Bucket(7), new Bucket(7)};
    // I'm only taking 100 values because otherwise this would take a really long time.
    var combos = Combos(letters, 0, buckets).Take(100);
    foreach (var combo in combos)
    {
        Console.WriteLine(combo);
    }
}

public class Bucket : List<char>
{
    public int MaxLoad {get; private set;}
    public Bucket(int capacity) : base(capacity)
    {
        MaxLoad = capacity;
    }
}

// Define other methods and classes here
IEnumerable<string> Combos(IList<char> letters, int currentIndex, Bucket[] buckets)
{
    if(currentIndex == letters.Count){
        yield return string.Join("|", buckets.Select(b => string.Join(",", b)));
        yield break;
    }
    var currentLetter = letters[currentIndex];
    foreach (var bucket in buckets)
    {
        if(bucket.Count < bucket.Capacity)
        {
            bucket.Add(currentLetter);
            foreach (var possibility in Combos(letters, currentIndex + 1, buckets))
            {
                yield return possibility;
            }
            bucket.Remove(currentLetter);
        }
    }
}

Пример вывода: 

a,b,c,d,e,f|g,h,i,j,k,l|m,n,o,p,q,r,s|t,u,v,w,x,y,z
a,b,c,d,e,f|g,h,i,j,k,l|m,n,o,p,q,r,t|s,u,v,w,x,y,z
a,b,c,d,e,f|g,h,i,j,k,l|m,n,o,p,q,r,u|s,t,v,w,x,y,z
a,b,c,d,e,f|g,h,i,j,k,l|m,n,o,p,q,r,v|s,t,u,w,x,y,z
a,b,c,d,e,f|g,h,i,j,k,l|m,n,o,p,q,r,w|s,t,u,v,x,y,z
a,b,c,d,e,f|g,h,i,j,k,l|m,n,o,p,q,r,x|s,t,u,v,w,y,z
a,b,c,d,e,f|g,h,i,j,k,l|m,n,o,p,q,r,y|s,t,u,v,w,x,z
a,b,c,d,e,f|g,h,i,j,k,l|m,n,o,p,q,r,z|s,t,u,v,w,x,y
a,b,c,d,e,f|g,h,i,j,k,l|m,n,o,p,q,s,t|r,u,v,w,x,y,z
a,b,c,d,e,f|g,h,i,j,k,l|m,n,o,p,q,s,u|r,t,v,w,x,y,z
a,b,c,d,e,f|g,h,i,j,k,l|m,n,o,p,q,s,v|r,t,u,w,x,y,z
a,b,c,d,e,f|g,h,i,j,k,l|m,n,o,p,q,s,w|r,t,u,v,x,y,z
a,b,c,d,e,f|g,h,i,j,k,l|m,n,o,p,q,s,x|r,t,u,v,w,y,z
a,b,c,d,e,f|g,h,i,j,k,l|m,n,o,p,q,s,y|r,t,u,v,w,x,z
a,b,c,d,e,f|g,h,i,j,k,l|m,n,o,p,q,s,z|r,t,u,v,w,x,y
a,b,c,d,e,f|g,h,i,j,k,l|m,n,o,p,q,t,u|r,s,v,w,x,y,z
a,b,c,d,e,f|g,h,i,j,k,l|m,n,o,p,q,t,v|r,s,u,w,x,y,z
a,b,c,d,e,f|g,h,i,j,k,l|m,n,o,p,q,t,w|r,s,u,v,x,y,z
a,b,c,d,e,f|g,h,i,j,k,l|m,n,o,p,q,t,x|r,s,u,v,w,y,z
a,b,c,d,e,f|g,h,i,j,k,l|m,n,o,p,q,t,y|r,s,u,v,w,x,z
a,b,c,d,e,f|g,h,i,j,k,l|m,n,o,p,q,t,z|r,s,u,v,w,x,y
a,b,c,d,e,f|g,h,i,j,k,l|m,n,o,p,q,u,v|r,s,t,w,x,y,z
a,b,c,d,e,f|g,h,i,j,k,l|m,n,o,p,q,u,w|r,s,t,v,x,y,z
a,b,c,d,e,f|g,h,i,j,k,l|m,n,o,p,q,u,x|r,s,t,v,w,y,z
a,b,c,d,e,f|g,h,i,j,k,l|m,n,o,p,q,u,y|r,s,t,v,w,x,z
a,b,c,d,e,f|g,h,i,j,k,l|m,n,o,p,q,u,z|r,s,t,v,w,x,y
...

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

Но имейте в виду, что в конечном итоге вы получите Много комбинаций-вполне возможно, больше, чем компьютер может генерировать за любой разумный промежуток времени, независимо от алгоритмической эффективности. Например, если оценка Винсента 10^12 верна, то при использовании приведенного выше кода потребуется примерно год. Вы можете оптимизировать его до месяца или около того. Распараллеливание может занять до недели на действительно сильном компьютере.
4

Это проблема рекурсии.

Если бы я хотел найти список всех наборов длины n, содержащих некоторую букву, самый простой способ думать об этом-это список всех наборов длины n-1, которые не содержат эту букву, объединенную с набором [букв] для каждого из них, чтобы избежать дубликатов, вы отбрасываете все элементы, которые вы ранее сделали

Например, если бы я хотел найти число двух буквенных комбинаций в наборе [A-F], ответ заключается в том, чтобы взять каждый элемент и найти комбинации из этого. Итак, скажем, я хочу найти все комбинации, содержащие A, которые затем будут [A][B-F], затем скажем, я хочу найти все комбинации, содержащие B, но не A, чтобы продолжить это могло быть [B][C-F], делая это для всех букв a-f, вы получите все возможные комбинации из двух букв A-F, так что теперь эта комбинация становится вашим хвостом списка для трех буквенных комбинаций.

Вы бы добавили a ко всем двум буквенным комбинациям, которые не содержат A, а затем вы бы добавили b для всех двух буквосочетаний, которые не содержат a или b, и продолжить это, чтобы получить все три буквосочетания.

Вы можете продолжать этот алгоритм, чтобы иметь столько уровней, сколько вы хотите, и он найдет комбинации всех элементов набора заданной длины

Я знаю, что вы не ищете код, но вот реализация c# 

public IList<string> Combos(IList<string> elements, int level)
    {
        if (level == 1)
        {
            return elements;
        }
        var combinations = new List<string>();
        var previousCombos = Combos(elements, level - 1);
        for (var i = 0; i < elements.Count; i++)
        {
            previousCombos.ToList().ForEach(item =>
            {
                if (!elements.Take(i+1).Any(item.Contains))
                {
                    combinations.Add(item + elements[i]);
                }
            });
        }
        return combinations;
    }
Просто предупреждаю, что это невероятно неэффективно, на самом деле я думаю, что это экспоненциальный алгоритм, поэтому не используйте его на больших наборах данных или размерах, или ваши вычисления займут вечность.
0