yarkov
@yarkov
Проект "Жизнь после смерти" - lifeafterdeath.ru

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

Ребята, спасайте. Не могу придумать алгоритм. Исходная задача такая: Переменные: 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 будут одинаковыми ситуациями, и в нашу таблицу внесется лишь одна из них (думаю не столь важно какая именно). В случае если я нажму галочку "с учетом порядка" - то в таком случае это уже будут разные ситуации и обе будут внесены в нашу таблицу. Стек уже будет привязываться к номеру позиции. У меня тяжеловато с комбинаторикой, так что я вряд ли смогу определить примерное количество подобных сочетаний.

Действительно не могу ничего придумать. Бьюсь два часа уже.
  • Вопрос задан
  • 2806 просмотров
Пригласить эксперта
Ответы на вопрос 3
@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.
Ответ написан
Mrrl
@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 миллионов.
Ответ написан
aush
@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;
    }
}
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы
от 100 000 до 200 000 ₽
VENTRA Москва
До 100 000 ₽
ATI.SU Санкт-Петербург
от 160 000 ₽
29 июл. 2021, в 03:08
5000 руб./за проект
26 июл. 2021, в 20:10
15000 руб./за проект
28 июл. 2021, в 22:43
12000 руб./за проект