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

Note that there are some explanatory texts on larger screens.

plurals
  1. POWrite a function to cycle through subsets by adding/deleting elements
    primarykey
    data
    text
    <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>
    singulars
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. PTQuestion
    1. This table or related slice is empty.
    1. USDaniel
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    2. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POWrite a function to cycle through subsets by adding/deleting elements
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. POWrite a function to cycle through subsets by adding/deleting elements
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. POWrite a function to cycle through subsets by adding/deleting elements
      1. This table or related slice is empty.
      1. VTUpMod
    1. COWhich operations are allowed on set S?
      singulars
      1. POWrite a function to cycle through subsets by adding/deleting elements
      1. USLuka Rahne
    2. COI don't fully understand the imposed restrictions - what prevents us from generating all the possible combinations of n and n+1 elements (out of the total 2n+1 elements) and printing them out?
      singulars
      1. POWrite a function to cycle through subsets by adding/deleting elements
      1. This table or related slice is empty.
    3. CO@Grigory: Because you can only add or remove one element at a time, and you can only use sets of size n or n+1. So you can't go from [1] to [2] or from [1,3] to [2].
      singulars
      1. POWrite a function to cycle through subsets by adding/deleting elements
      1. USDaniel
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

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