элегантное решение. работа со строками.

[vlad7]

ааа, их просто сложить надо было,

Спасибо за разъяснение

Самое интересное, что каждый следующий массив уже содержит в себе предыдущий. Можно формировать массив строк для случая n = k и дергать оттуда значения. Массив можно формировать по алгоритму сортировки, реализованном в BidirectionalIterator из STL (next_permutation и prev_permutation).

А это сложнее не будет в рекурсивной реализации?

 

[AS0kol]

imho, рекурсии накладные.

Может я и ошибаюсь. Вот формула для получения общего количества комбинаций

 

[vlad7]

imho, рекурсии накладные.

Может я и ошибаюсь. Вот формула для получения общего количества комбинаций

Все правильно. Это просто просуммированные размещения. Все гениальное просто



Есть же люди на этом форуме. Нормально объяснят, укажут на ошибки

 

[Supostat]

imho, рекурсии накладные.

Может я и ошибаюсь. Вот формула для получения общего количества комбинаций

Так никто и не обьяснил, чем же рекурсия накладная?
Может мой код - это не рекурсия?

 

[AS0kol]

Ну как бы никто и не должен

⚠ Тільки зареєстровані користувачі бачать весь контент та не бачать рекламу.

.

 

[Supostat]

Ну как бы никто и не должен

⚠ Тільки зареєстровані користувачі бачать весь контент та не бачать рекламу.

.

Я никого и не заставляю, просто спросил. Т.к. видится мне, что в данном, конкретном случае, Вы неправы насчёт накладности рекурсии. Вот в упор не вижу накладок... Вы видите?

 

[AS0kol]

Я вижу решение без рекурсий.

 

[Supostat]

Я вижу решение без рекурсий.

Это Вы молодец, но я спрашивал о другом.
Я может плохо выразился? О каких копиях массивов идёт речь, если никаких копий массивов создавать не нужно? Копии ССЫЛОК на массив, это есть.
Если длина строки 10 символов, то результирующий массив распухает, но во время вычисления ничего такого с памятью у меня не происходит. Да и откуда, если глубина рекурсии будет всего 10 вызовов? И это по Вашему большие накладные расходы?

 

[AS0kol]

Это Вы молодец, но я спрашивал о другом.
Я может плохо выразился? О каких копиях массивов идёт речь, если никаких копий массивов создавать не нужно? Копии ССЫЛОК на массив, это есть.
Если длина строки 10 символов, то результирующий массив распухает, но во время вычисления ничего такого с памятью у меня не происходит. Да и откуда, если глубина рекурсии будет всего 10 вызовов? И это по Вашему большие накладные расходы?

Про стек думал? О копиях массивов никто не говорил вроде. Если расматривать цель задачи, как вывод вариантов в консоль, то можно обойтись и без массивов.



Впрочем, я, наверное загнул. Ресурсы жрет постепенно, но не пока не упала (минут пять работает со строкой "abcdefghijklmnopqrstuvwxyz"). Немного изменил программу: заменил combinations.Add(substring.ToString()); на Console.WriteLine(substring.ToString()); Оставлю на ночь, посмотрим, что получится.

 

[Supostat]

Ну так стек зависит от "глубины" рекурсии, правильно? В моём примере она никогда не превышает количества символов в заданной строке. А на 1 вызов там 1 переменная "i" ну и ссылки на 3 массива, плюс что там ещё своего служебного довешивает сама среда. Вроде так...

 

[BFG-9000]

рекурсия ко всему прочему, хранит в памяти все копии массивов в промежуточных вычислениях.

Это, извините, у Вас, молодой человек, руки немного не так заточены.
Кто Вас заставляет копировать массив на каждом шаге? Модифицируете массив, рекурсивно вызываетесь и после возврата откатываете назад модификацию. Дешево и сердито. Не надо даже ссылок или указателей передавать если массив глобальный, всех затрат - 4 байта в стеке на адрес возврата на кадом уровне рекурсии. Посчитайте возможную глубину при очень скромном стеке в 16 килобайт
Про недостатки рекурсии блеет тот, кто не умеет ею пользоваться Ну так такие люди в придачу не проверяют результат оператора new

 

[AS0kol]

#include <stdio.h>
#include <time.h>

int const gLoopCount = 1000000;
typedef long long int(*TTestProc)(int aNumber);

long long int getFactorialThroughLoop(int aNumber) {
  if (aNumber < 2) return 1;
  int lResult = 2;
  int lRangeMember = 3;
  while (lRangeMember <= aNumber) {
    lResult *= lRangeMember++;
  }
  return lResult;
}

long long int getFactorialThroughRecursion(int aNumber) {
  if (aNumber < 2) return 1;
  return aNumber * getFactorialThroughRecursion(aNumber - 1);
}

void executeTestFunction(TTestProc aFunction, int aNumber, char* aFunctionName) {
  clock_t lClock = clock();
  int lIndex;
  for (lIndex = 0; lIndex < gLoopCount; lIndex++) {
    aFunction(aNumber);
  }
  printf("%s: elapsed time is %d ticks\n", aFunctionName, clock() - lClock);
  return;
}

int main(int argc, char *argv[]) {
  executeTestFunction(getFactorialThroughLoop, 10, "getFactorialThroughLoop");
  executeTestFunction(getFactorialThroughRecursion, 10, "getFactorialThroughRecursion");
  printf("Press any key to exit...");
  getchar();
}