Перебор последовательности динамической длины. (важно)

[juky88]

Подскажите пожалуйста!!!
Есть массив чисел размером n. Из этого массива нужно перебрать возможные последовательности длиной k.
Длина последовательности может быть различной.
Например, миссив {0,1,2,3,4,5,6,7,8,9}. Устанавливаем длину последовательности k=2. Должны получить: 0,1; 0,2; 0,3;...0,9; 1,2; 1,3; 1,4;...1,9
и т.д. А если пользователь ввёл длину последовательности k=3, то получим: 0,1,2; 0,1,3; 0,1,4;...0,1,9; 0,2,3; 0,2,4;...0,2,9; 0,3,4; 0,3,5;...0,3,9; и т.д
Последовательность 0,1,2 = 0,2,1, поэтому учитываем только 0,1,2.

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

Заранее спасибо большое за помощь!!!

[BBB]

Если бы последовательность была постоянной, то всё просто ... А тут ...что длина последовательности может быть любой.

Не очень понимаю мысль. Да, длина может быть любой, но после того, как она установлена, она же уже постоянна на протяжении данной итерации.

[Romeo]

BBB, здесь человек другое имел ввиду. Задачу ведь можно решать в лоб. Если, к примеру, в условиях задачи указано фиксированное число 2, в качестве k, то задача решается двумя вложенными циклами с дополнительными внутренними проверками. Если в условии указано k=3, то тремя вложенными циклами и т.д. Проблема возникает тогда, когда условие содержит слова "k вводится с клавиатуры". В этом случае указать в программе k вложенных циклов, когда k ещё не известно не получится, как следствие, решение задачи "в лоб" не проходит.

juky88, твоя задача нахождения всех подстановок "Цэ из эн по ка" стара, как мир. Я в своё время придумал следующий алгоритм для её решения. Берём целое число типа int. В нём, как известно, 32 бита, если ты программируешь под 32-битную платформу. Расцениваем каждый бит этого числа как то, входит ли число из исходного массива с соответствующим индексом в текущее подмножество или нет (0 или 1). Если мы запустим цикл от нуля до 2^n - 1, и на каждом шаге будем раскладывать счётчик на биты, то получим все возможные подмножества исходного массива. Тебе останется только выбрать из них все множества с количеством элементов = k, это и будут все искомые подстановки. Если в исходном массиве будет элементов больше, чем 32, то можно воспользоваться счётчиком типа long int, увеличив свои возможно до 64-х элементов. Если элементов может быть вообще ОЧЧЕНЬ много, то стоит заменить биты числа на динамический массив из char'ов, в которых будет лежать 0 или 1. В этом случае нам даже не придётся выделять биты с помощью маски, но зато придётся обеспечить инкремент такого импровизированного представления счётчкика. Это, кстати, не сложно. Вот набросок программки, которая выводи все подмножества (писал на скорую руку без компилятора, так что могут быть мелкие ошибки). Предлагаю тебе модифицировать программу, чтобы среди всех подмножеств выбирались те, которые длинной k.

Код: Выделить всё

int n, k;
// input n and k
...

int* arrInput = new int [n];
// input elements of arrInput
...

char* arrBits = new char [n];
memset(arrBits, 0, n*sizeof(char));

while (true)
{
   // Incrementing bit array
   for (int bi = 0; bi < n; ++bi)
   {
      if (arrBits[bi] == 1)
      {
         arrBits[bi] = 0;
      }
      else
      {
         arrBits[bi] = 1;
         break;
      }
   }

   if (bi == n)
      break; // all elements are examined

   for (int i = bi; i < n; ++i)
   {
      if (arrBits[i] == 1)
      {
         std::cout << arrInput[i] << " ";
      }
   }
   std::cout << std::endl;
}