Geek Answers Handbook

Write a function to cycle through subsets by adding / removing elements

Challenge: Start with a set S size 2n + 1 and a subset A of S size n. You have the addElement(A,x) and removeElement(A,x) functions that can add or remove an A element. Write a function that cycles through all subsets S size n or n + 1, using only these two operations on A

I realized that there are (2n + 1 select n) + (2n + 1 select n + 1) = 2 * (2n + 1 select n) the subsets I need to find. So here is the structure for my function:

 for (int k=0; k<2*binomial(2n+1,n); ++k) { if (k mod 2) { // somehow choose x from SA A = addElement(A,x); printSet(A,n+1); } else // somehow choose x from A A = removeElement(A,x); printSet(A,n); } }

The binomial(2n+1,n) function simply gives a binomial coefficient, and the printSet function prints the elements of A so that I can see if I hit all the sets.

I do not know how to select an item to add or remove. I tried many different things, but I did not get anything that worked at all.

For n = 1, a solution was found here, which I found:

 for (int k=0; k<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); } }

and the conclusion for S = [1,2,3] and A=[1] :

 [1,2] [2] [2,3] [3] [3,1] [1]

But even if this works for n = 2, I cannot do it. Can someone help me with this?

+4
source share
2 answers

This is not a solution, as it is another way to think about a problem.

Make the following chart:

  • Vertices are all subsets of S sizes n or n+1 .
  • There is an edge between v and w if two sets differ by one element.

For example, for n = 1 you get the following loop:

  {1} --- {1,3} --- {3} | | | | {1,2} --- {2} --- {2,3}

Your problem is to find the Hamiltonian cycle :

A Hamiltonian cycle (or Hamiltonian scheme) is a cycle into an undirected graph that visits each vertex exactly once, and also returns to the starting vertex. Determining whether such paths and cycles in graphs is a Hamiltonian trajectory problem that is NP-complete.

In other words, this problem is complex.

There are several theorems that give sufficient conditions for the existence of a Hamiltonian cycle in a graph (for example, if all vertices have degree at least N/2 , where n is the number of vertices), but none of them knows right away that this graph has a Hamiltonian cycle.

You can try one of the countless algorithms to determine if a Hamiltonian cycle exists. For example, from a wikipedia article to Hamilton's Path Problem :

A trivial heuristic algorithm for finding Hamiltonian paths is to build the path abc ... and expand it until it becomes impossible; when the path abc ... xyz cannot be expanded anymore, because all neighbors of z are already on the path, one returns one step, removing the edge yz and the path with the other neighbor of y; if none of the options creates a Hamiltonian trajectory, then take a step backward, removing the edge xy and expanding the path using another neighbor x, etc. This algorithm will certainly find the Hamiltonian path (if any), but it works exponentially.

Hope this helps.

Good news . Although the problem with the Hamiltonian cycle is complex in general, this graph is very good: it is bipartite and (n+1) -regular. This means that there may be a pleasant solution for this particular schedule.

Bad news . After a short search, it turned out that this problem is known as a mid-level hypothesis, and it seems that it arose around 1980. As far as I can tell, the problem is still open at all, but it was checked by the computer for n <= 17 (and I found the preprint from 12/2009, requiring confirmation of n=18 ). These two pages contain additional information about the problem and links:

+5
source

Similar things are described in the book Knuth Vol 4A (which, despite the superiority of Charles Strauss, is now open to real novels). I think your request is satisfied with the monotonous binary gray code section described in section 7.2.1.1. There is an online preprint with a PDF version at http://www.kcats.org/csci/464/doc/knuth/fascicles/fasc2a.pdf

-1
source

More articles:


All Articles