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. :)

You didn't mention this, but I assume from your question that you would only want each item in the set to be used once, for instance in the set A,B,C,D,E: AAAA is not a valid pairing? — Ryan Guill, Jun 09 '09 at 18:03
do you consider ABCDE an appropriate element in your set or not? — Tetsujin no Oni, Jun 09 '09 at 18:27
Why did you title this the way you did and list "compare" as a tag? Are you generating the powerset in order to test whether an particular string set is in it or not? If so, there may be more efficient hueristics to get that information. — Bert F, Jun 09 '09 at 21:14
hi, thanks for your answer. Basically i have a large set of data that i have categorized. this data consists of persons and each person may have categories such as publications or place of birth or undergraduate studies. now each category may have one or more values. for example someone may have undergraduate studies from New York and Berlin. What i want is to select any field i wish (or all) from the thousands that exist of all persons in my databsase and try and mine any relationships between them. so if someone selects 5 fields to mine then i want the program to search for any combination — , Jun 10 '09 at 20:07

score 5 · Answer 1 · edited May 23 '17 at 11:48

5

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

edited May 23 '17 at 11:48

Community

1
1

answered Jun 09 '09 at 18:11

Michael Borgwardt

342,105
78
482
720

great! that is exactly what i was looking for. i just need to make a function in a thread to try and find any set from a given larger set of values! ::D – Jun 10 '09 at 20:10

score 0 · Answer 2 · answered Jun 09 '09 at 18:07

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.

score 0 · Answer 3 · answered Jun 09 '09 at 18:13

0

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?

answered Jun 09 '09 at 18:13

Dario

48,658
8
97
130

score 0 · Answer 4 · answered Jun 09 '09 at 19:05

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); }
}

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

4 Answers4