Create possible pairs irrespective of order in a indefinite set of values.

Question

What i am trying to figure out is an algorithm that will create possible pairs irrespective of order in a indefinite set of values.

for example let's say the set is A,B,C,D,E

then possible sets are

AB AC AD AE BC CD DE

but... i also want pairs of more than 2 values.

for example

ABC ABD ABE BCD BCE

but also ABCD or ABCE. The problem here is that i want to make a method with input an array of Strings STring[] and the output would be a list of Strings in pair of 2,3.... up to number of values -1.

If anyone has a thought of a solution please help. :)

Answer 1

This is one of the most computation-intensive things you could do. This will not scale well at all with an even remotely large set of data.

It's really not practical for indefinite sets. You could limit the pairs which can be generated, and therefore make this scale better.

Answer 2

It seems you want to construct a power set. This question is essentially the same, look there for answers.

Answer 3

What you want to create is some kind of power set of your input's permutations.

Java's iterator concept theoretically allows infinite sequences.

But what has your question to do with comparing?

Answer 4

Not the most efficient, but a solution:

import java.util.Arrays;
import java.util.Collection;
import java.util.HashSet;
import java.util.Set;

public class PowersetTest {

public static void main(String [] args){
 Set<Set<String>> sets =  permute(Arrays.asList("a","b","c","d","e"));
 for (Set<String> item : sets){
  System.out.printf("Set: %s%n", item.toString());
 }
}
    static public <T> Set<Set<T>> permute (Collection<T> items){
      Set<Set<T>> result = new HashSet<Set<T>>();
      for (final T item : items){
        Set<T> subsetElements = filter(items, new Predicate<T>(){public boolean apply(T f){ return (f!=item);}});
        if (subsetElements.size() > 0) {
          result.addAll(permute(subsetElements));
        }
        Set<T> temp = new HashSet<T>();
        temp.addAll(items);
        result.add(temp);
      }
      return result;
    }

  static public <T> Set<T> filter(Collection<T> items, Predicate<T> filter){ 
    Set<T> result = new HashSet<T>();
    for (T item : items){ 
      if (filter.apply(item)) {
        result.add(item);
      }
    }
    return result;
  }

  public interface Predicate<T>{ public boolean apply(T item); }
}