Science
Copyright © 2024 Jiri Kriz, www.nosco.ch
Snippet so7594360
Back to Overview

Algorithm to find all possible 'StringPairGroups' in Java?


import java.util.ArrayList;
import java.util.List;

/**
 * http://stackoverflow.com/a/7594360
 * @author Jiri
 */
class StringPairGroups {    
    public static class Pair {
        public String s1, s2;
        public Pair(String s1, String s2) {
            this.s1 = s1; this.s2 = s2;
        }
        public String toString() {
            return s1 + s2;
        }
    }
    
    public static class Group {
        public List<Pair> pairs = new ArrayList<Pair>();
        public Group(Pair p) {pairs.add(p);}
    }    
    
    public List<Group> getGroups(String[] strings, int order) {
        List<Group> groups = new ArrayList<Group>();
        for (int i = 0; i < strings.length; ++i) {
            for (int j = 0; j < strings.length; ++j) {
                if (i != j) {
                    Pair p = new Pair(strings[i], strings[j]);
                    if (order == 1) {
                        groups.add(new Group(p));
                    }
                    else {
                        String[] strings2 = new String[strings.length - 2];
                        for (int k = 0, k2 = 0; k < strings.length; ++k) {
                            if (k != i && k != j) {
                                strings2[k2++] = strings[k];
                            }
                        }
                        List<Group> groups2 = getGroups(strings2, order - 1);
                        for (int k = 0; k < groups2.size(); ++k) {
                            Group g = new Group(p);
                            groups.add(g);
                            Group g2 = groups2.get(k);
                            g.pairs.addAll(g2.pairs);
                        }
                    }
                }
            }            
        }
        return groups;
    }

    public List<Group> getAllGroups(String[] strings) {
        List<Group> groups = new ArrayList<Group>();
        for (int order = 1; order <= strings.length/2; ++order) {
            List<Group> groups2 = getGroups(strings, order); 
            groups.addAll(groups2);
        } 
        return groups;
    }

    public void printGroups(List<Group> groups) {
        for (int i = 0; i < groups.size(); ++i) {
            System.out.print((i + 1) + ": ");
            List<Pair> pairs = groups.get(i).pairs;
            for (int j = 0; j < pairs.size(); ++j) {
                if (j > 0) {System.out.print(", ");}
                System.out.print(pairs.get(j));
            }
            System.out.println();
        }
    }

   public static void main(String[] args) {
        String strings[] = {"A", "B", "C", "D", "E", "F"}; 
        StringPairGroups G = new StringPairGroups();
        List<Group> groups = G.getAllGroups(strings);
        G.printGroups(groups);
     }
}