Timeline for Generating all possible subsets in order of sum
Current License: CC BY-SA 4.0
14 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 17 at 21:09 | history | bumped | CommunityBot | This question has answers that may be good or bad; the system has marked it active so that they can be reviewed. | |
| Apr 19 at 21:06 | history | bumped | CommunityBot | This question has answers that may be good or bad; the system has marked it active so that they can be reviewed. | |
| Mar 21 at 15:36 | comment | added | Ood | @BrendanMcKay I have tested the algorithm empirically and it seems to be just over O(n) per iteration on average, although there are outliers. So you are right that it might not be technically polynomial, but it does behave very well in practice. | |
| Mar 21 at 4:05 | comment | added | Brendan McKay | Note that it is only necessary to solve the problem for subsets of fixed size, since you can run all sizes in parallel with only $O(\log n)$ extra cost per iteration. | |
| Mar 21 at 4:03 | comment | added | Brendan McKay | I'm not sure the answer at stackexchange satisfies "polynomial time per iteration". | |
| Mar 20 at 16:20 | comment | added | Ood | @CommandMaster Thank you, that seems to be exactly my problem and the answer I am looking for! Too bad I did not find this earlier. | |
| Mar 20 at 15:08 | comment | added | Daniel Weber | See math.stackexchange.com/a/89453/752906 this Math Stack Exchange question and answer | |
| Mar 20 at 13:14 | comment | added | user1020406 | Is $O(n)$ per iteration and $O(n 2^n)$ total acceptable? If so, you can achieve this by using any $O(1)$ insert time heap to store the candidate sets. You start with the empty set on the heap, and then any time you take a set $S$ out, you insert $S \cup \{a\}$ for all $a$ larger than all $s \in S$ back to the heap. en.wikipedia.org/wiki/… | |
| Mar 20 at 11:10 | answer | added | BADJARA Mohamed el Amine | timeline score: -1 | |
| Mar 19 at 21:44 | comment | added | Max Alekseyev | It should be possible to get space complexity $O(2^{n/4})$ using the data structures suggested by Schroeppel and Shamir (1981). | |
| Mar 19 at 21:30 | history | edited | Ood | CC BY-SA 4.0 |
deleted 2 characters in body
|
| Mar 19 at 21:29 | history | edited | YCor | CC BY-SA 4.0 |
removed capitals from title
|
| S Mar 19 at 21:25 | review | First questions | |||
| Mar 20 at 7:22 | |||||
| S Mar 19 at 21:25 | history | asked | Ood | CC BY-SA 4.0 |