How to build a complex algorithm for combinatorics?

Question

Algorithms

Guys, save. I can't think of an algorithm. The initial task is as follows: Variables: 1. Number of positions (in my case it will be a number from 2x to 6) 2. The sum of all stacks (chips) 3. The step of changing the stack (chips) 4. With / without taking into account the order
After i I will set variables - the program will have to create a large table, in which there will be all situations of distribution of chips. Here is an example:
6 people; in total for all 3000 chips; step 10 chips. Regardless of order. The program starts with 10/10/10/10/10/2950 (let it be so that the stack size cannot be less than a step) then goes for example 20/10/10/10/10/2940 and then starts iterating over all possible combinations of stack sizes (BUT necessarily giving the same figure in the amount, which we will set as the sum of the stacks). In general, each stack will be a multiple of a step, and when stacks are swapped, there should be no overlap. Those. in this case, for example, 10/20/30/40/50/2850 and 30/40/2850/50/10/20 will be the same situations, and only one of them will be entered into our table (I think it’s not so important which one). If I click on the "taking into account the order" checkbox, then in this case these will already be different situations and both will be included in our table. The stack will already be tied to the position number.
I really can't think of anything. I've been fighting for two hours already.

Answer 1

Hmeeeeeee ... If you need a complete table of combinations, then combinatorics-combinatorics, and you have to sort through everything.
Take N-1 positions, and sequentially go through the possible stack sizes on each, throwing off the rest to the N-position? If you
look at the above example, then
something
like this : 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 And further on positions. Almost addition in a column, however.
If you need an implementation without regard to order, then you need to introduce the condition on the previous method that N + 1 position always contains more (or less, direction is not critical?) chips than N.

Answer 2

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] is set and fill(A,N,sum,sum-N+1,ord) is called, where N=6, sum=300, ord - true if order is taken into account and false if not accounting. I checked for N=5, sum=10 - there the number of options is acceptable. As far as I understand, for (6,300,true) there will be approximately 21 billion combinations (Comb(299,5)), and for (6,300,false) - at least 30 million.

Answer 3

The solution is "on the forehead", you can optimize:

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