[C#] Arrays - 21 задача


1
21.Write a program that reads two numbers N and K and generates all the combinations of K distinct elements from the set [1..N]. Example:

  N = 5, K = 2 -> {1, 2}, {1, 3}, {1, 4}, {1, 5}, {2, 3}, {2, 4}, {2, 5}, {3, 4}, {3, 5}, {4, 5}




Отговори



6

http://pastebin.com/57c2jJpb

Тук съм поместил две решения на проблема. Първото решение е закоментирано, само по себе си работи, но не извежда резултатите подредени, ами малко хаотично. Използван е кода на Грей, описан в SubsetSums.

Второто решение е рекурсивно, наподобява вариациите, които съм описал ТУК.

Разликата идва от това, че добаваме още една променлива CurrentNumber към метода, която да указва на следващото рекурсивно извикване, от кое число да започне, за да избегне повторенията. Именно повторенията различават комбинациите от вариациите.


от ivaylo.kenov (30760 точки)


11

Ето и моите решения: вариациикомбинациипермутацииРазгледайте разликите. Решенията са с рекурсия.

Ако някой е забравил комбинаториката - bg.wikipedia.org/wiki/Комбинаторика.


от jasssonpet (6814 точки)


0
Тоя next за какво си го ръгнал бре:), като винаги му подаваш 0-ла и не се променя никъде в рекурсията :) Иначе рекурсивните решения на задачата са най-често срещани. +1

от Prophian (1234 точки)

0
Трябва да е next + 1, но сигурно и така ще работи щом е постнато тук.

от nikola76 (1250 точки)



1
Генерирам всички подмножества от N елементи -> нататъка вече е лесно, селектирам всички К на брой единици в подмножеството и го разпечатвам.
http://pastebin.com/zfKaZ8xU
Приятно четене :)

от Prophian (1234 точки)


4
Не се различава много от задача 20, има само една допълнителна проверка за повтарящи се елементи.
http://pastebin.com/M6NyuTNt
(Има коментари в кода)

от psabinski (129 точки)


1
Решението за Комбинации: http://pastebin.com/tqGxmXH1

от werew (576 точки)


0
Ъм по-добре е да смениш int n = 5; int k = 2; със Console.WriteLine("Type n: "); int n = int.Parse(Console.ReadLine()); Console.WriteLine("Type k: "); int k = int.Parse(Console.ReadLine()); в смисъл то май няма много значение, но все пак друго си е рандом цифри :)

от Martin88 (209 точки)

0
Аз съм го тествал с други числа и просто не съм му сложил вход от конзолата. Мерси за предложението :))

от werew (576 точки)


2

http://www.codeproject.com/Articles/2781/Combinatorial-algorithms-in-C разгледайте тази тема, може да ви е много полезна.

Аз използвам част метода "NextIndeces(bool bReturnDublicate)" от класа "Combinations.cs"

Хубавото на този метод е:

    1. Лесен е за рабиране, без рекурсия и други по-сложни похвати.

    2. За дадена сегашна комбинация, връща следващата комбинация, а не всички наведнъж

    3. Модифицира масив от ИНДЕКСИ (arr {0, 1, 2, ...k}). Това позволява, взимайки сегашната комбинация от индекси,  да се достъпят елементите на всеки друг масив с същата дължина. Например за p от 1 до к, може да формираме сумата на p елемента от даден масив и да я сравним с дадена сума и ако двете суми са равни:

    - sumExists = true; return;

Ето го и моето решение с обяснения вътре(може би повече от нужното)

За да изпозлваме List<T> трябва да включим библиотеката System.Collections.Generic

http://pastebin.com/Qba9fnPe

 


от Stefanpu (404 точки)


0
Моето решение е модификация на решението на проблема с подмножествата, с побитови операции Първо пълня масив с числата от 1 до N. След това проверявам комбинациите с K числа и ги добавям в един стринг След, като напълня стринга го добавям в List, който сортирам, защото комбинациите не са във възходящ ред и го принтирам със String.Join()
https://github.com/martinivanovit/SimpleProjects/blob/master/Combos
Не е от най-добрите решения, но мисля, че работи коректно

от Mahata231 (1351 точки)


0
Може ли някой да ми каже къде бъркам - повтарят ми се някои числа, а уж логиката ми е вярна?
http://pastebin.com/rwtS89a7

от stann1 (1378 точки)


0
Edit: оправих, го - ъпдейтвам рекурсията със start+1 вместо с индекса (i+1) Хубаво казват лекторите - като не знаеш добре рекурсия не я ползвай! :)

от stann1 (1378 точки)

0
да ама и някой каза тук : "За да разбереш рекурсията трябва да разбереш рекурсията" Много ми харесва. ;)

от gparlakov (884 точки)



0
Здравейте, ето го и моето решение: http://pastebin.com/Ct4k1g2N :)

от Plamen.Minkov (216 точки)


0

Привет,

Моето решение е рекурсивно.

Методът се терминира ако  исканата комбинация е с дължина  2 - тогава се генерират с два вложени фор цикъла като взимам първия елемент от първия цикъл и втория от вложения и ги записвам в List < List <int> >.
Ако е с дължина > 2 тогава във един фор цикъл взимам първия (после втория,третия...до където може) елемент и викам метода
(в който може да се зададе началния елемент от който да почне цомбинацията) с начало втория (третия, четвъртия...) елемент и с дължина - (дължината -1) . После вмъквам запазения елемент отпред във всеки един от генерираните подмножества/sequences в кода/List<int> 

 

http://pastebin.com/qpzvMX8L 
И вътре има коментарчета


от gparlakov (884 точки)