Databases
StackOverflow2013
Postsdbo
POWrite a function to cycle through subsets by adding/deleting elements
Body
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POWrite a function to cycle through subsets by adding/deleting elements
    text
    copied!<p>Problem: Start with a set <code>S</code> of size 2n+1 and a subset <code>A</code> of <code>S</code> of size n. You have functions <code>addElement(A,x)</code> and <code>removeElement(A,x)</code> that can add or remove an element of <code>A</code>. Write a function that cycles through all the subsets of <code>S</code> of size n or n+1 using just these two operations on <code>A</code>.</p> <p>I figured out that there are (2n+1 choose n) + (2n+1 choose n+1) = 2 * (2n+1 choose n) subsets that I need to find. So here's the structure for my function:</p> <pre><code>for (int k=0; k&lt;2*binomial(2n+1,n); ++k) { if (k mod 2) { // somehow choose x from S-A A = addElement(A,x); printSet(A,n+1); } else // somehow choose x from A A = removeElement(A,x); printSet(A,n); } } </code></pre> <p>The function <code>binomial(2n+1,n)</code> just gives the binomial coefficient, and the function <code>printSet</code> prints the elements of <code>A</code> so that I can see if I hit all the sets.</p> <p>I don't know how to choose the element to add or remove, though. I tried lots of different things, but I didn't get anything that worked in general.</p> <p>For n=1, here's a solution that I found that works:</p> <pre><code>for (int k=0; k&lt;6; ++k) { if (k mod 2) { x = S[A[0] mod 3]; A = addElement(A,x); printSet(A,2); } else x = A[0]; A = removeElement(A,x); printSet(A,1); } } </code></pre> <p>and the output for <code>S = [1,2,3]</code> and <code>A=[1]</code> is:</p> <pre><code>[1,2] [2] [2,3] [3] [3,1] [1] </code></pre> <p>But even getting this to work for n=2 I can't do. Can someone give me some help on this one?</p>
 

Querying!

 
Guidance
An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload