Перечислите все возможные комбинации k целых чисел от 1 ... n (n выберите k)

Question

Без особой причины я решил поискать алгоритм, который выдает все возможные варианты выбора k целых чисел от 1 до n, где порядок между k целыми числами не имеет значения (n выбирает k штук).

По той же самой причине, которая вовсе не является причиной, я также реализовал ее в C #. Мой вопрос:

Видите ли вы ошибку в моем алгоритме или коде? И, что более важно, Вы можете предложить лучший алгоритм?

Пожалуйста, обратите больше внимания на алгоритм, чем на сам код. Это не самый красивый код, который я когда-либо писал, хотя скажите, если увидите ошибку.

РЕДАКТИРОВАТЬ: Alogirthm объяснил -

• Мы держим k индексов.
• Это создает k вложенных для циклов, где индексом цикла i являются индексы [i].
• Имитирует k для циклов , где индексы [i + 1] принадлежат циклу, вложенному в цикл индексов [i].
• индексы [i] идут от индексов [i - 1] + 1 к n - k + i + 1.

КОД:

public class AllPossibleCombination
{
    int n, k;
    int[] indices;
    List<int[]> combinations = null;

    public AllPossibleCombination(int n_, int k_)
    {
        if (n_ <= 0)
        {
            throw new ArgumentException("n_ must be in N+");
        }
        if (k_ <= 0)
        {
            throw new ArgumentException("k_ must be in N+");
        }
        if (k_ > n_)
        {
            throw new ArgumentException("k_ can be at most n_");
        }

        n = n_;
        k = k_;
        indices = new int[k];
        indices[0] = 1;
    }

    /// <summary>
    /// Returns all possible k combination of 0..n-1
    /// </summary>
    /// <returns></returns>
    public List<int[]> GetCombinations()
    {
        if (combinations == null)
        {
            combinations = new List<int[]>();
            Iterate(0);
        }
        return combinations;
    }

    private void Iterate(int ii)
    {
        //
        // Initialize
        //
        if (ii > 0)
        {
            indices[ii] = indices[ii - 1] + 1;
        }

        for (; indices[ii] <= (n - k + ii + 1); indices[ii]++)
        {
            if (ii < k - 1)
            {
                Iterate(ii + 1);
            }
            else
            {
                int[] combination = new int[k];
                indices.CopyTo(combination, 0);
                combinations.Add(combination);
            }
        }
    }
}

Я прошу прощения за длинный вопрос, возможно, он подходит для поста в блоге, но я хочу узнать мнение сообщества здесь.

Спасибо,
Асаф

Answer 1

В C ++ задана следующая процедура:

template <typename Iterator>
inline bool next_combination(const Iterator first, Iterator k, const Iterator last)
{
   /* Credits: Thomas Draper */
   if ((first == last) || (first == k) || (last == k))
      return false;
   Iterator itr1 = first;
   Iterator itr2 = last;
   ++itr1;
   if (last == itr1)
      return false;
   itr1 = last;
   --itr1;
   itr1 = k;
   --itr2;
   while (first != itr1)
   {
      if (*--itr1 < *itr2)
      {
         Iterator j = k;
         while (!(*itr1 < *j)) ++j;
         std::iter_swap(itr1,j);
         ++itr1;
         ++j;
         itr2 = k;
         std::rotate(itr1,j,last);
         while (last != j)
         {
            ++j;
            ++itr2;
         }
         std::rotate(k,itr2,last);
         return true;
      }
   }
   std::rotate(first,k,last);
   return false;
}

Затем вы можете выполнить следующее:

std::string s = "123456789";
std::size_t k = 3;
do
{
   std::cout << std::string(s.begin(),s.begin() + k) << std::endl;
}
while(next_combination(s.begin(),s.begin() + k,s.end()));

Answer 2

Асаф,

Вы просите нас оценить ваш алгоритм, но вы не объясняете свой алгоритм - даже в комментариях к коду. Итак, вы хотите, чтобы каждый потратил час или больше на обратное проектирование алгоритма из кода, чтобы мы могли понять ваш вопрос, прежде чем ответить на него?

Пожалуйста, измените ваш вопрос, чтобы объяснить ваш алгоритм.

Одна вещь очевидна - объем памяти вашего кода ужасен. Даже при скромных значениях n число комбинаций легко исчисляется миллиардами, что потребует больше памяти, чем у большинства компьютеров. Кроме того, вы используете динамически растущие массивы, которые по мере роста перераспределяют и копируют себя. Плюс ваша программа генерирует подмножества в разных массивах и объединяет их. В общем, вашей программе потребуется много раз объем памяти, который в идеале был бы необходим для хранения списка, и она будет тратить большую часть своего времени на копирование данных туда и обратно.

Если вы должны иметь все значения в массиве одновременно, по крайней мере начните с вычисления необходимого размера массива - n! / (н-к)! / к! - а затем просто заполняя его.

Еще лучше был бы код, который "лениво" просто вычислял каждый элемент последовательности, как это было необходимо. См. этот вопрос на боковой панели связанных вопросов

Answer 3

Этот парень, кажется, проделал серьезную работу в комбинаторике с использованием C # (CodeProject):

Перестановки, комбинации и вариации с использованием C # Generics

Answer 4

Вот относительно простая / эффективная программа nCr, которую я недавно написал на C:

main(n,k){float t=0,r=1;for(scanf("%d, %d",&n,&k);t++<k;r*=(1+n-t)/t);printf("%.0f\n",r);}

Хорошо ... читаемая версия. =] (Не уверен, что 1: 1 соответствует приведенному выше.)

void nCr(int n, int k) {
    float curK = 0, r = 1;
    while(curK < k) {
        ++curK;
        printf("%.0f\n", r);
        r *= (1 + n - curK) / curK;
    }
}

Вместо печати вы можете yield или что-то еще (я не знаю C #) в вашем списке.