如何找出0-1000内30个整数的所有组合

Question

我正在寻找一种方法来查找 numbersArray 中 0-1000 之间的 30 个数字的所有组合。

        For example 1st combination is: 0,1,2,3,4,5,6......29,30
        For example 2nd combination is: 0,2,3,4,5,6,7......30,31
        For example 2rd combination is: 0,3,4,5,6,7,8......31,32

然后继续寻找所有的组合。任何数字在 30 个数字系列中只能出现一次。

这里非常重要的细节是，如果可以在创建这些组合时立即使用它们。换句话说，不是先存储组合然后再次遍历它们。这意味着双倍的迭代量？

谢谢！

    void findcombinations()
    {
        //Declaring the array with 1000 indexes
        //The number of indexes can be up to 100,000 indexes
        int[] numbersArray = new int[1000];
        for (int i = 0; i < numbersArray.Length; i++)
        {
            numbersArray[i] = i; //Assign number from 0-1000
        }

        //How to find all combinations of 30 numbers between: 0-1000?
        //For example 1st combination is: 0,1,2,3,5,6,7......29,30
        //For example 2nd combination is: 0,2,3,5,6,7,8......30,31
        //For example 2rd combination is: 0,3,5,6,7,8,9......31,32

        //How to dynamically find all combinations of a group of 30 numbers between 0-1000?
        
        //Not perheps exactly use the below approach because that would mean that we already have filled the
        //Array with the combinations.

        //I am trying to see if there is a dynamic approach where the combinations are produced right away so 
        //They can be used straight away as they are produced?
        int[,] allCombinations = new int[???,30]; ///??? How many combinations of 30 numbers 
        for (int i = 0; i < allCombinations.Length; i++)
        {
            for (int i2 = 0; i2 < allCombinations.GetLength(i); i2++)
            {
                //Do something with the combination of numbers here
            }
        }
    }

Answer 1

这里有解决方案：

using System;
using System.Collections.Generic;

namespace combinatory
{
    public class Combinations
    {
        private readonly int n;
        private readonly int k;
        private readonly int[] combination;

        public Combinations(int n, int k)
        {
            if (n <= 0) throw new ArgumentException("n argument must be greater than 0", nameof(n));
            if (k <= 0) throw new ArgumentException("k argument must be greater than 0", nameof(k));
            if (n < k) throw new ArgumentException("k argument must be greater or equals to n", nameof(k));

            this.n = n;
            this.k = k;

            combination = new int[k];

            for (int i = 0; i < k; i++)
            {
                combination[i] = i;
            }
        }

        public IEnumerable<int[]> Get()
        {
            yield return combination;
            while (TrySetNextCombination())
            {
                yield return combination;
            }
        }

        private bool TrySetNextCombination()
        {
            int incrementableIndex = findFirstIncrementableIndex();
            if (incrementableIndex < 0) return false;
            var value = combination[incrementableIndex];
            for (int i = incrementableIndex; i < k; i++)
            {
                combination[i] = ++value;
            }
            return true;
        }

        private int findFirstIncrementableIndex()
        {
            int index = k - 1;
            int threshold = n - 1;
            while (index >= 0)
            {
                if (combination[index] < threshold) return index;
                index--;
                threshold--;
            }
            return index;
        }
    }
}

class Combinations 有一个接受 n 和 k 参数的构造函数。 n是集合中的元素个数，k是子集中的元素个数。它有 Get 方法，它枚举所有组合。它的内存效率非常高，因为它只需要一个 k 整数数组。关键点是初始化第一个组合，然后计算下一个。

您可以这样使用它：

using System;

namespace combinatory
{
    class Program
    {
        static void Main(string[] args)
        {
            var combinations = new Combinations(6, 3);
            foreach (var comb in combinations.Get())
            {
                foreach (var v in comb)
                {
                    Console.Write(" ");
                    Console.Write(v);
                }
                Console.WriteLine();
            }
        }
    }
}

这是输出：

Answer 2

事实上，如果您只需要组合的数量，可以进行数学计算：

n！ / (p! . (n - p)!)

其中n为总人数（1000），p为抽取人数（30）。

来源：https://en.m.wikipedia.org/wiki/Combination

如何找出0-1000内30个整数的所有组合

How to find all combinations of 30 integers within 0-1000

c#

arrays

combinations

combinatorics