Conversation started May 29, 2014 at 4:03.
rolfl
rolfl
May 29, 2014 04:03
Hi, just checking in, code is right, and it should not produce the same results as the quoted-block
Let me rephrase that...
The code shoud not return the same content as the quoted block.
The quoted block is unique combinations.
He wants to change it so that the unique no longer applies.
Mat's Mug
Mat's Mug
code returns 15 values (lists of values actually) whether the input is new[] {1,2,3} or new[]{1,2,2,3,3} - so that's correct?
rolfl
rolfl
no....
Mat's Mug
Mat's Mug
user image
rolfl
rolfl
Someone needs to point out that counting in binary and and combinations, are best friends
Mat's Mug
Mat's Mug
I'm hitting a wall with this code, I've never written something like this (permutations), my head is about to explode... I think recursion is the correct way to do this, but I just can't seem to get it. Trying to implement it with yield return.... not working :(
rolfl
rolfl
May 29, 2014 04:12
No... you're doing it wrong, but I am no good with C#
There's a trick.
It's the fastest way to do it, and it will work with yield nicely
Let me explain .... you listeneing?
@Mat'sMug ... ?
Mat's Mug
Mat's Mug
sorry.. yeah
(wife just arrived)
rolfl
rolfl
Combinations:
- you have a set of numbers.
put them in an array
Mat's Mug
Mat's Mug
new[]{1,2,3}
gotcha
rolfl
rolfl
each number is either in the combination, or it is not.
Each number has a 'state', on, or off.
Now, that reminf you of something?
Mat's Mug
Mat's Mug
hmm allright
rolfl
rolfl
May 29, 2014 04:15
Yes, bits.
Consider your numbers {1,2,3}.
Now consider binary counting with 3 bits: 
000
001
010
011
100
...
To get combinations, you create an integer that logically has as many bis as data memebers.... 
int limit = 1 << size
Mat's Mug
Mat's Mug
so... this isn't about recursion at all?
rolfl
rolfl 
for (int i = 0; i < limit; i++) {
    for (int bit = 0; bit < size; bit++) {
        if (i & (1 << bit) = 1) {
            .... then array[bit] is in the combination
Mat's Mug
Mat's Mug
right
and if it is in the combination, you yield return it
rolfl
rolfl
Not quite.
You need to do that inside the i loop, not inside the bit loop.
So, before the bit loop you create a list to store your combination.
then add the data to the list inside the bit loop.
Mat's Mug
Mat's Mug
right, because you're yielding an IEnumerable<int> to return an IEnumerable<IEnumerable<int>>
rolfl
rolfl
May 29, 2014 04:20
then yield the list outside the bit loop
Now, the i loop does not need to be a loop, it can be an int that you use to yield the combination, then you increment it for the next()
in other words, your only state you need is the current i, and the limit.
Mat's Mug
Mat's Mug
aren't you assuming the values are contiguous here?
Phrancis
Phrancis
I'm going to say my mind is blown and leave it at that.
rolfl
rolfl
Array indexes are always contiguous.
Mat's Mug
Mat's Mug
duh
rolfl
rolfl
The only time you run in to problems is when you have more members in the set than you have bits in your integer.
Mat's Mug
Mat's Mug
May 29, 2014 04:23
that seems much, much, much more simpler than OP's O(n^n) solution (making this up, ...but there's definitely an exponential in the complexity there)
rolfl
rolfl
But, you can safely use a signed 64bit long, and the user will never know even if they have more than 64 set memebers
Because, the yield process is not instantaneous, and, they will have to do it .... oh, about 9,223,372,036,854,775,807 times.
and, they will probably die before that matters.
Mat's Mug
Mat's Mug
I'm so bookmarking this conversation and eventually implementing it.
bit-shifting stuff always gets me nervous
Phrancis
Phrancis
I don't understand it but it sounds wicked smart o_O
2
rolfl
rolfl
Feel free.
 
Conversation ended May 29, 2014 at 4:27.