Generate teams of a group

Question

I want to generate all possible teams of a group of n things taken k at a time, for example "abcd" = ab,ac,ad... without duplicates. I have written this, but it generates all permutations of a string. I have written a method to check if two strings have the same characters, but I don't know if this is the correct way.

package recursion;

import java.util.Arrays;

public class Permutations2 {

    public static void main(String[] args) {
        perm1("", "abcd");
        System.out.println(sameChars("kostas","kstosa"));
    }


    private static void perm1(String prefix, String s) {
        int N = s.length();
        if (N == 0){
            System.out.println(prefix);
        }
        else {
            for (int i = 0; i < N; i++) {
                perm1(prefix + s.charAt(i), s.substring(0, i) + s.substring(i+1, N));
            }
        }
    }

    private static boolean sameChars(String firstStr, String secondStr) {
        char[] first = firstStr.toCharArray();
        char[] second = secondStr.toCharArray();
        Arrays.sort(first);
        Arrays.sort(second);
        return Arrays.equals(first, second);
    }
}

Possible duplicate: http://stackoverflow.com/questions/4240080/generating-all-permutations-of-a-given-string — sdasdadas, Jun 04 '13 at 21:23

score 3 · Answer 1 · answered Jun 04 '13 at 21:24

3

You are describing a power set.

Guava has an implementation.

answered Jun 04 '13 at 21:24

Jean Logeart

52,687
11
83
118

It seems like a power set gives all permutations, not just the ones of length `k`. Obviously it could be used for this purpose (only keep the sets that are length `k`) but I wonder if there's something that's an even better fit. – Daniel Kaplan Jun 04 '13 at 21:43
[implementation](http://docs.guava-libraries.googlecode.com/git/javadoc/com/google/common/collect/Sets.html#powerSet%28java.util.Set%29) is no longer working. – jay.sf Jun 02 '20 at 11:40

score 0 · Answer 2 · answered Jun 04 '13 at 21:41

May you want the Enumerating k-combinations.

private static void combinate(String s, String prefix, int k) {
    if (s.length() < k) {
        return;
    } else if (k == 0) {
        System.out.println(prefix);
    } else {
        combinate(s.substring(1), prefix + s.charAt(0), k - 1);
        combinate(s.substring(1), prefix, k);
    }
}

public static void main(String[] args) {
    combinate("abcd", "", 2);
}

Output:

ab
ac
ad
bc
bd
cd

See Introduction to Programming in Java - Recursion - Robert Sedgewick and Kevin Wayne

score 0 · Answer 3 · answered Jun 04 '13 at 21:59

This should work without recursion:

private static void perm(String s) {
   char[] arr = s.toCharArray();     
   for (int i = 0; i < s.length() - 1; i++) {
      for(int j = i + 1; j < s.length(); j++) {
         System.out.println(String.valueOf(arr[i]) + String.valueOf(arr[j]));
      }
   }
}

It's O(n**2).

Generate teams of a group

3 Answers3

Linked