CODEWITHSUNDEEP
javacompareset
alex
alex

Reputation:

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

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

Upvotes: 2

Views: 345

Answers (4)

Tetsujin no Oni
Tetsujin no Oni

Reputation: 7375

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

Upvotes: 0

Dario
Dario

Reputation: 49218

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?

Upvotes: 0

Michael Borgwardt
Michael Borgwardt

Reputation: 346476

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

Upvotes: 5

Zack Marrapese
Zack Marrapese

Reputation: 12091

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.

Upvotes: 0

Related Questions