[C#] Търси се логика за намиране на комбинации от n/N елемента


3
Имам масив с 'N' елемента и се опитвам да измисля функция която да проверява да проверява всяко едно субмасивче с 'n' елементи (тоест масивче което взема само част от 'N' елементите). Искам 'n' и 'N' да са променливи за да мога да използам функцията многократно при различни условия.
Подредбата на елементите не е от значение. За предпочитане е функцията да не минава втори път през същите елементи, когато те са подредени различно. Иначе ще стане много тежко.
Алтернатива е да се направи същата функция за числата които НЕ влизат в комбинациите. Когато [n*2 > N] тази логика ще е по-щадяща за компютъра.
Досега не съм направил почти никакъв прогрес.
Моля помогнете ми. Не е нужно да пишете цялото решение - просто ми трябва някаква насока, или жокер.




Отговори



1

Ако имаш фиксиран 'n' може и да го направиш хамалската с вложени цикли, но тъй като го искаш по-абстрактно, според мен няма как без рекурсия, което прави алгоритъма труден за обяснение :D, или може би не толкова, метод вика себе си при някакво ограничение. Мога да ти предложа едно решение, което ми се наложи да използвам на последния изпит. Трябва да го попреправиш малко за да ти върши работа.

В случая ограничението (дъното) е когато променливата 'length' (в случая твоята 'n') стане 1, при условие, че се намалява с 1ца при всяка итерация на вложения foreach ... Другото е магия laugh


от nikolay.n (924 точки)


0
жалко че затвори Темата :( предполагам говориш за задача 9 от условни конструкции.
Ето моето решение без рекурсия :)
1. Създаваме Списък в който ще запишем комбинациите м/у елементите. Всяка една комбинация е списък с нейните елементи
var listOfCombinations = new List

от micro3x (57 точки)


0
Преди малко решавах задачата Dancing Bits, където има търсене на субмасив (три еднакви числа) в масив. Едно общо решение мога да ти предложа:
for (int i = 0; i < M - N; i++) { // променливи int j = 0; for ( j = i ; j < i+N; j++) { // някаква логика } // друга логика }

от ivan.yosifov (679 точки)


0
Това е подходящо когато 'n' не е променлива. Аз обаче търся код който да работи еднакво добре както за 2 от 6 елемента, така и за 3, 4, или 5 от 6-те елемента.
// Не съм сигурен дали може да стане с обикновени цикли.
// Не разбирам съвсем примера ти, Ivan Yosifov, а ми стана любопитно. Ясно ми е че не е това за което питам, но не разбирам как с 2 цикъла ще намериш комбинация от 3 числа. За такова нещо не трябва ли да има и трети цикъл?

от lokiko91 (790 точки)

0
За да се търсят три числа, за j се задава j = i + 1 и във вътрешния цикъл се сравняват array[i] с array[j]. Аз просто малко го модифицирах за да отговаря на твоето условие, но явно не съм го разбрал напълно. :)

от ivan.yosifov (679 точки)


0

Първо трябва да уточниш дали търсиш Вариация или Комбинация на елементите. Ето тук може да прочетеш повече. След като имаш яснота по този въпрос решението със сигурност може лесно да се намери.


от wnvko (3123 точки)


0

Ето едно решение за генерирането на комбинации без повторение и не е рекурсивно решението, но сякаш е малко хамалско ;д Минаваме през всички възможни числа за комбинация, проверяваме дали е нарастваща, така всъщност изключваме повторенията на комбинациите и ако е нарастваща текущата комбинация, тогава я отпечатваме. Ето и кода: http://pastebin.com/Uh3rmC97


от mbelev (2312 точки)


0
Благодаря на всички ви, най-вече на Николай Николов. Неговият вариант ще ми свърши най-добра работа.

от lokiko91 (790 точки)