CODEWITHSUNDEEP
java
user2268216
user2268216

Reputation: 1

Generate teams of a group

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

Upvotes: 0

Views: 113

Answers (3)

Paolof76
Paolof76

Reputation: 909

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

Upvotes: 0

Paul Vargas
Paul Vargas

Reputation: 42040

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

Upvotes: 0

Jean Logeart
Jean Logeart

Reputation: 53839

You are describing a power set.

Guava has an implementation.

Upvotes: 3

Related Questions