creating a list of subsets from N elements

[luc comeau]

Hi everyone, first time posting in this particular forum, hope i chose the right place

Ok so i have this problem; I am given a vector containing Strings in them say for example,"name","Telephone","address"..etc (personal information bascially).
To simplify the problem i think maybe ill just make each string in the array correspond to a letter in the alphabet ie.name=a,telephone=b,address=c.

Ok so say i am passed a vector with "a","b","c", i need to be able to create all the sets of these, without repeating any letters in a set.So basically my answer to this should just be;
a,b,c,ab,ac,bc,abc

But my method to do this must also be able to handle any amount of inputs, not just three, so i could have a,b,c,d,e...then must be able to find all the sets of those as well.

I started this using for loops but i think i began to realize that it didnt work for N inputs, because each time i wanted more inputs i needed more for loops, so its bascially useless what ive done so far.Maybe recursion or something might be useful, anyone have any ideas?

Thanks for patiently reading, hope to hear some suggestions!

[Stephen Huey]

Sounds like a school assignment...yeah, I'd say go for recursion. If you need to double check your work (make sure you haven't added the same thing twice to a set), you might try using the java.util.Set class (or rather, maybe java.util.HashSet or something like that).

[luc comeau]

hey,
lol, its not a school assignment at all, haha, i wish it was, im actually writing a program at work, this is a minor part to it but its essential for forward progress in the project.I asked a few people here at work and they say they may have some notes from their Algorithms and Data structures classes that might be able to help me, but we'll see i supose.

I infact am not a huge fan of recursion, cause it actually requires more effort to think up the logic for it,(poor me eh) haha but i guess i can give it a try.As for the java.util.set class and the hashSet, ill give them a looking at, still any other ideas would be much appreciated!
thanks again
[ February 21, 2005: Message edited by: luc comeau ]

[Igor Stojanovic]

Hi luc,

I think you should use Varargs (Methods That Allow Variable-Length Parameter Lists)


The following class defines a method that accepts a vararg, and invokes the same method passing it first several arguments and then fewer arguments. The arguments come in as an array.

public class Varargs {
 
public static void main(String...args) {
 
   Varargs test = new Varargs();
 
   //call the method
 
   System.out.println(test.min(9,6,7,4,6,5,2));
 
   System.out.println(test.min(5,1,8,6));
 
}
 
/*define the method that can accept any number
 
of arguments.
 
*/
 
public int min(Integer...args) {
 
      boolean first = true;
 
      Integer min = args[0];
 
 
      for (Integer i : args) {
 
         if (first) {
 
            min = i;
 
            first = false;
 
         } else if (min.compareTo(i) > 0) {
 
            min = i;
 
         }
 
      }
 
   return min;
 
}
 
}
 
The output is
 
2
 
1
 
 

When combined with the for each loop, varargs are very easy to use.


Note that varargs are new to SDK 5.0, so you need to compile for that version of Java to use them.



kind regards
Igor
[ February 21, 2005: Message edited by: Igor Stojanovic ]

[Michael Dunn]

class CombinationsAll
{
  String startCombo = "abcd";
  public CombinationsAll()
  {
    for(int x = 1; x <= startCombo.length(); x++)
    {
      int[] arr = new int[x];
      for(int y = 0; y < x; y++) arr[y] = y;
      getStartCombos(arr);
    }
    System.exit(0);
  }
 
  private void getStartCombos(int arr[])
  {
    String thisCombo = "";
    for(int x = 0; x < arr.length ; x++) thisCombo += startCombo.charAt(arr[x]);
    getCombos("",thisCombo);
    if(arr[0] == (startCombo.length()-1)-(arr.length-1-0)) return;
    if(arr[arr.length-1] == startCombo.length()-1)
    {
      for(int i = 0; i < arr.length;i++)
      {
        if(arr[i] == (startCombo.length()-1)-(arr.length-1-i))
        {
          arr[i-1]++;
          for(int ii = i; ii < arr.length; ii++)
          {
            arr[ii] = arr[ii-1] + 1;
          }
          break;
        }
      }
    }
    else
    {
      arr[arr.length-1]++;
    }
    getStartCombos(arr);
  }
  private void getCombos(String str1, String str2)
  {
    int i = str2.length()-1;
    if(i < 1) System.out.println(str1+str2);
    else for(int ii = 0; ii <= i; ii++) getCombos(str1 + str2.substring(ii,ii+1),
                 str2.substring(0, ii) + str2.substring(str2.length() - (i-ii)));
  }
  public static void main(String[] args) {new CombinationsAll();}
}

[luc comeau]

hi everyone

Igor, thanks for the effort with the Varargs, i should have mentioned before that i am not using 1.5, i have started this project before it was released so im using 1.4.2, but it i cant figure something out i will consider that, thanks

Michael,I gave your code a run and the only thing that appears wrong withit is that it is writing out all "permutations" of the String "abcd"(well its not really wrong but in my situation it is),i infact need the combinations of "abcd" where ordering doesnt matter.So where your program counts ab,ba as two different elements, i infact would only count them as one, like i wouldnt consider them at all as being different.

Im going to try and trace through your code and see if i can figure out how to change this, but if its easy to fix and repost please feel free, but thanks for the time u took to post that in the first place, much appreciated !
P.s- has anyone ever heard of the "Banker's Sequence"
iv done a little research and aparently this sequence is the fastest way to approach this problem, but iv yet to find any implementation of it in java.
It does the subsets int he way you would suspect
if you had abcd, its would orde them like this
{a,b,c,d},{ab,ac,ad},{bc,bd},{cd},{abc,abd},{acd},{bcd},{abcd}
just a thought, maybe this might strike some more ideas.
[ February 22, 2005: Message edited by: luc comeau ]

[Michael Dunn]

try this one then

class CombinationSets
{
  String set = "abcd";
  public CombinationSets()
  {
    for(int x = 1; x <= set.length(); x++)
    {
      int[] array = new int[x];
      for(int y = 0; y < x; y++) array[y] = y;
      printSets(array);
    }
  }
  public void printSets(int[] arr)
  {
    String thisCombo = "";
    while(true)
    {
      thisCombo = "";
      for(int x = 0; x < arr.length ; x++) thisCombo += set.charAt(arr[x]);
      System.out.println(thisCombo);
      if(arr[0] == (set.length()-1)-(arr.length-1)) break;
      if(arr[arr.length-1] == set.length()-1)
      {
        for(int i = 0; i < arr.length;i++)
        {
          if(arr[i] == (set.length()-1)-(arr.length-1-i))
          {
            arr[i-1]++;
            for(int ii = i; ii < arr.length; ii++) arr[ii] = arr[ii-1] + 1;
            break;
          }
        }
      }
      else arr[arr.length-1]++;
    }
  }
  public static void main(String[] args) {new CombinationSets();}
}

[David Harkness]

If it helps, realize that what you're effectively doing is counting in binary. Each element in the original list is a bit representing whether it is in or out of any given subset, so you're writing out all possible bit combinations. If there were three elements, the subsets would be

000 -- you probably want to omit the empty subset
001
010
011
100
101
110
111

You could use a recursive algorithm if the number of elements is small enough, but you can certainly rewrite it non-recursively.

Sorry, I only have time for that much right now, but hopefully it can give you enough to solve it.

[luc comeau]

hi everyone again,

David, i first would like to say thats exactly what i was working on yesterday, seems that i always come up with the same ideas as you as u post them, I wrote up some code that does the binary representation of them, for the sake of helping others wanting to do this ill post the code, or if you were intrested;

 public static void output(int[] string, int position) {
      int[] temp_string = new int[length];
      int index = 0;
      int i;
      for (i = 0; i < length; i++)
{
  if ((index < position) && (string[index] == i))
    {
      temp_string[i] = 1;
      index++;
    }
  else
    temp_string[i] = 0;
}
      for (i = 0; i < length; i++)
System.out.println( temp_string[i]);
      if (i%length==0)
System.out.println("\r");
    }
  
  public static void generate(int[] string, int position, int positions) {
    if (position < positions)
      {
if (position == 0)
  {
    for (int i = 0; i < length; i++)
      {
string[position] = i;
generate(string, position + 1, positions);
      }
  }
else
  {
    for (int i = string[position - 1] + 1; i < length; i++)
      {
string[position] = i;
generate(string, position + 1, positions);

      }
  }
      }
    else
      output(string, positions);
  }
  
  public static void main (String[] args)
  {
    length = 3;  /*this is hard coded for now but can be any value */
    for (int i = 0; i <= length; i++)
      {
int[]  string = new int[length];
generate(string, 0, i);

      }
    System.exit(0);
  }
 

I havn't yet decided what i want to do with these binary representations, but for the most part this thread has accomplished what i asked !! Thanks

As for Michael, ill give your code a try and see if maybe i can find some way to incorporate your idea it may be useful for a later stage of my coding, non the less, thanks so much !
[ February 23, 2005: Message edited by: luc comeau ]

[Luke Nezda]

Last solution offered is basically a copy/paste from the C++ code from the December 2000 academic paper "Efficiently Enumerating the Subsets of a Set" by J. Loughry, J.I. van Hemert, and L. Schoofs if anyone is interested in more details on the Banker's Sequence and this implementation by its original authors.