Как построить сложный алгоритм на комбинаторику?

Question

[Алексей Ярков]

Ребята, спасайте. Не могу придумать алгоритм. Исходная задача такая: Переменные: 1. Количество позиций (в моем случае это будет число от 2х до 6ти) 2. Сумма всех стеков (фишек) 3. Шаг изменения стека (фишек) 4. С учетом/без учета порядка

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

6 человек; в сумме на всех 3000 фишек; шаг 10 фишек. Без учета порядка. Программа начинает с 10/10/10/10/10/2950 (пусть будет так, что размер стека не может быть меньше шага) затем идет например 20/10/10/10/10/2940 и далее начинает перебирать всевозможные сочетания размеров стека (НО обязательно дающие в сумме одну и ту же цифру, которую мы зададим в качестве суммы стеков). В общем каждый стек будет кратным шагу и при перемене стеков местами - не должно быть совпадений. Т.е. в этом случае например 10/20/30/40/50/2850 и 30/40/2850/50/10/20 будут одинаковыми ситуациями, и в нашу таблицу внесется лишь одна из них (думаю не столь важно какая именно). В случае если я нажму галочку "с учетом порядка" - то в таком случае это уже будут разные ситуации и обе будут внесены в нашу таблицу. Стек уже будет привязываться к номеру позиции. У меня тяжеловато с комбинаторикой, так что я вряд ли смогу определить примерное количество подобных сочетаний.

Действительно не могу ничего придумать. Бьюсь два часа уже.

Answer 1

[Archet]

Хмэээээээ... Если нужна полная таблица сочетаний, то комбинаторика-комбинаторикой, а перебрать придется все.

Взять N-1 позиций, и последовательно перебрать возможные размеры стеков на каждой, скидывая в N-позицию остаток?
Если смотреть по приведенному примеру, то примерно так:
10/10/10/10/10/2950
10/10/10/10/20/2940
...
10/10/10/10/2940/20
10/10/10/10/2950/10
10/10/10/20/10/2940
10/10/10/20/20/2930
...
10/10/10/20/2940/10
10/10/10/30/10/2930
И далее по позициям. Почти сложение в столбик, однако.

Если нужна реализация без учета порядка, то на предыдущий метод нужно ввести условие, что N+1 позиция всегда содержит больше (или меньше, направление не критично же?) фишек, чем N.

Answer 2

[Mrrl]

static int sstep;
       static void FindAll(int N,int sum,int step,bool ord){
            sstep=step;
            sum/=step;
            fill(new int[N],N,sum,sum-N+1,ord);
        }
        static void output(int[] A){
              Console.Write("{0}",A[0]*sstep);
              for(int i=1;i<A.Length;i++) Console.Write("/{0}",A[i]*sstep);
              Console.WriteLine();
        }

        static void fill(int[] A,int N,int sum,int smax,bool ord) {
            if(N==0 && sum==0) {
                output(A);
                return;
            }
            if(N==0 || sum<N) return;
            int smin=ord ? 1 : (sum-1)/N+1;
            N--;
            for(A[N]=smin;A[N]<=smax;A[N]++) {
                fill(A,N,sum-A[N],ord ? sum-N+1 : A[N],ord);
            }
        }

Задаётся A=new int[N], и вызывается fill(A,N,sum,sum-N+1,ord), где N=6, sum=300, ord - true, если с учётом порядка и false, если без учёта. Я проверял для N=5, sum=10 - там число вариантов приемлемо. Насколько я понимаю, для (6,300,true) будет примерно 21 миллиард комбинаций (Comb(299,5)), а для (6,300,false) - не меньше 30 миллионов.

Comments

[Алексей Ярков]

N это размер шага?

[Алексей Ярков]

И что такое output(A);? Студия ругается на эту строку.

[Mrrl]

Нет, N - число игроков. Размер шага здесь считается равным 1, при печати все числа придётся умножить на 10. output(A) - функция, которая должна печатать массив A, или делать с ним что-то ещё - вам виднее, что именно. Её напишите сами.

[Алексей Ярков]

Благодарю за помощь, но это немного не то что требовалось. Ваш код ищет все возможные комбинации чисел, сумма которых в совокупности будет равна int sum. А надо чтобы она шаг учитывала. То есть выдавала строку для
sum = 1000
step = 10
N = 6

10/10/10/10/10/950
10/10/10/10/950/10
10/10/10/950/10/10
10/10/950/10/10/10
10/950/10/10/10/10
950/10/10/10/10/10
.........................................
10/10/10/10/20/940

Это при условии что ord = true. А если ord = false, то программа должна принять первые 6 строк как одинаковые и вернуть любую из них.

[Mrrl]

А что Вам мешает при печати умножить все числа из массива на 10?

[Алексей Ярков]

А я умножал. Вы же писали это выше. Но выводит то все равно не так как надо. Я уже почти написал как надо. Скоро выложу.

[Алексей Ярков]

pastebin.com/pZusMUmS
Вот что вышло

[Mrrl]

Алексей: Или я чего-то очень не понимаю, или она будет печатать
10/10/10/10/10/950
20/20/20/20/20/900
...
190/190/190/190/190/50
- и больше ничего (если порядок не важен). То есть, 5 чисел всегда будут одинаковы.

[Алексей Ярков]

Сейчас именно так как вы говорите. Моя задача привести к тому, чтобы она печатала 10/10/10/10/10/950
10/10/10/10/20/940
и т. п.

[Mrrl]

А мой код что выдаёт (если в нём сделать вывод не на консоль, а в правильное место)?

[Алексей Ярков]

Ваш выдаёт массив 24/24/26/26 и дальше в таком роде. Поиграл с данными - начал выдавать 1/1/1/97

[Алексей Ярков]

Вы безусловно очень помогли, но это опять не то ((( Нужно выводить именно так как я указывал. То есть если элементов 6, сумма 1000 и шаг 10, то выводить строки
10-10-10-10-10-950
10-10-10-10-20-940
10-10-10-10-30-930
И т. д.
Количество элементов может быть от 2 до 6.
Строки выше это без сохранения порядка.
Если с сохранением, то
10-10-10-10-10-950
10-10-10-10-950-10
10-10-10-950-10-10
10-10-950-10-10-10
10-950-10-10-10-10
950-10-10-10-10-10
10-10-10-10-20-940
10-10-10-20-940-10
И т. д.

Думаю понятно объяснил...
Я как только не пробовал ваш код подогнать - не выходит ничего.

[Mrrl]

Про первый порядок - понятно, он лексикографический. Например, для (4,10,1) должно получиться
1,1,1,7
1,1,2,6
1,1,3,5
1,1,4,4
1,2,2,5
1,2,3,4,
1,3,3,3
2,2,2,4
2,2,3,3
Правильно?
Но вот со вторым понять сложно. Ведь перестановки бывают не только циклическими. Уже для примера 1,1,1,1,2,94 их будет 30 штук. В каком порядке их надо вывести?

[Алексей Ярков]

Разберу пример с 10 фишками, шагом - 1 фишкой и 3мя игроками. Вот что получается если порядок не учитывать:
1-1-8
1-2-7
1-3-6
1-4-5
2-2-6
2-3-5
2-4-4
3-3-4
Все, 8 оригинальных строк. Все остальное - будет дублироваться (без учета порядка, т.е. просто сравнивая цифры: 1-1-8 и 1-8-1 - здесь будет одно и то же).
Если же рассмотреть тоже самое, но с учетом порядка. То получим:
1-1-8
1-8-1
8-1-1
1-2-7
1-7-2
2-1-7
2-7-1
7-1-2
7-2-1
...
В общем все значения где 2 одинаковые цифры - получится 3 варианта перестановки. В тех случаях, где все 3 цифры разные - получается 6 вариантов перестановок.
Получилось бы: 6*4+3*4=36 строк

[Mrrl]

Если порядок не учитывать, код такой:

static int sstep;

static void output(int[] A) {
Console.WriteLine(string.Join("/",Array.ConvertAll(A,(x => (x*sstep).ToString()))));
}

static void fill(int[] A,int idx,int N,int sum) {
if(idx==N-1) {
A[idx]=sum;
output(A);
return;
}
int first=idx==0 ? 1 : A[idx-1];
int smax=sum/(N-idx);
for(A[idx]=first;A[idx]<=smax;A[idx]++) fill(A,idx+1,N,sum-A[idx]);
}

static void FindAll(int N,int sum,int step) {
sstep=step;
sum/=step;
if(sum

[Mrrl]

if(sum < N) return;
fill(new int[N],0,N,sum);
}

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

[Mrrl]

А вот как выглядит output для перестановок при сохранении порядка:

static bool ord;

static void output(int[] A) {
if(ord) outputAll((int[])A.Clone(),0);
else outputOne(A);
}

static void outputAll(int[] B,int n) {
if(n==B.Length) {
outputOne(B);
return;
}
for(int i=n;i < B.Length;i++) {
Array.Sort(B,n,B.Length-n);
if(i > n && B[i]==B[i-1]) continue;
int a=B[i]; B[i]=B[n]; B[n]=a;
outputAll(B,n+1);
}
}
static void outputOne(int[] B) {
Console.WriteLine(string.Join("/",Array.ConvertAll(B,x => (x*sstep).ToString())));
}

Переменная ord заполняется в начале работы.

Answer 3

[aush]

Решение "в лоб", можете пооптимизировать:

internal class Program
{
    private static void Main(string[] args)
    {
        foreach (var combination in GenerateCombinations(3, 5, 1))
        {
            foreach (var i in combination)
            {
                Console.Write(i + ", ");
            }
            Console.WriteLine();
        }
        Console.WriteLine("----------------");

        foreach (var combination in GenerateUniqueCombinations(3, 5, 1))
        {
            foreach (var i in combination)
            {
                Console.Write(i + ", ");
            }
            Console.WriteLine();
        }

        Console.ReadLine();
    }

    private static List<List<int>> GenerateUniqueCombinations(int stacksCount, int totalAmount, int step)
    {
        var generatedCombinations = GenerateCombinations(stacksCount, totalAmount, step);

        var dicts = new List<Dictionary<int, int>>();
        foreach (var combination in generatedCombinations)
        {
            var dict = new Dictionary<int, int>();
            foreach (var i in combination)
            {
                if (dict.ContainsKey(i))
                {
                    dict[i]++;
                }
                else
                {
                    dict[i] = 1;
                }
            }
            if (!dicts.Any(d => DictionaryEquals(d, dict)))
            {
                dicts.Add(dict);
            }
        }

        return dicts.Select(d =>
        {
            var r = new List<int>();
            foreach (var key in d.Keys)
            {
                if (d[key] == 1)
                {
                    r.Add(key);
                }
                else
                {
                    r.AddRange(Enumerable.Repeat(key, d[key]));
                }
            }
            return r;
        }).ToList();
    }

    private static bool DictionaryEquals(Dictionary<int, int> x, Dictionary<int, int> y)
    {
        foreach (var key in x.Keys)
        {
            if (!y.ContainsKey(key))
            {
                return false;
            }

            if (x[key] != y[key])
            {
                return false;
            }
        }

        foreach (var key in y.Keys)
        {
            if (!x.ContainsKey(key))
            {
                return false;
            }

            if (x[key] != y[key])
            {
                return false;
            }
        }

        return true;
    }

    private static List<List<int>> GenerateCombinations(int stacksCount, int totalAmount, int step)
    {
        var result = new List<List<int>>();

        if (stacksCount > 1)
        {

            for (var i = 1; i < totalAmount / step; ++i)
            {
                var add = i * step;

                foreach (var generated in GenerateCombinations(stacksCount - 1, totalAmount - add, step))
                {
                    generated.Insert(0, add);
                    result.Add(generated);
                }
            }
        }
        else
        {
            result.Add(new List<int> { totalAmount });
        }

        return result;
    }
}