Блог

В настоящее время у меня есть следующий код для создания перестановок букв в строке. Мне было интересно, каким наиболее эффективным способом может быть преобразование его в комбинации, где порядок не имеет значения, вместо этого?

 public class Permutation {
public static void main (String[] args) {
    permute("ABCD");
}

public static void permute(String full) {
    if (full == null || full.length() == 0) {
        System.out.println("You must provide a string of length > 0");
            return;
        }
        permute("",full);
    }

private static void permute(String prefix, String remaining) {
    if (remaining.length() == 0) {
        System.out.println(prefix);
        return;
    }
    for (int i = 0; i < remaining.length(); i  ) {
        permute(prefix   remaining.charAt(i),remaining.substring(0, i)   remaining.substring(i   1, remaining.length()));

    }
}
 

}

Заранее благодарю вас!

Вы можете создать Stream<int []> множество комбинаций ( int [] это массив с количеством элементов для каждого типа).

Поток возвращает все комбинации с повторением любого размера:

 static Stream<int []> combinationsStream(final int... numElems) {
    final int numCombinations = Arrays.stream(numElems)                 // the number of solutions is
            .map(n -> n   1)                                            // possibles sizes
            .reduce(1, (a, b) -> a * b);                                // product

    final int[] queue = Arrays.stream(numElems).map(i -> -1).toArray(); // for every item take n elements
    final int[] i = new int[]{0};                                       // volatile (final) integer
    final Function<int [], int []> next = o -> {                        // compute the next combination
        while (true) {
            if (i[0] == numElems.length) {                              // if is the last position
                i[0] -= 1;                                              // we will back
                return queue;                                           // but it's a combination
            }
            queue[i[0]]  = 1;                                           // take one more of i[0]-th element
            if (queue[i[0]] > numElems[i[0]])                           // if no more of this
                queue[i[0]--] = -1;                                     // reset and go back
            else
                i[0]  = 1;                                              // if not, go forward
        }
    };
    return Stream.iterate(null, next::apply)                            // iterate getting next over and over
            .skip(1)                                                    // avoid the seed (null)
            .limit(numCombinations);                                    // limit the stream to combs number
}
 

например, комбинации из 3 яблок и 2 апельсинов являются:

 combinationsStream(3, 2)
    .forEach((int[] xs) -> System.out.println(Arrays.stream(xs).mapToObj(Integer::toString).collect(joining(", "))));
 

с выходом

 0, 0
0, 1
0, 2
1, 0
1, 1
1, 2
2, 0
2, 1
2, 2
3, 0
3, 1
3, 2
 

конечно, вы можете отфильтровать любое ограничение, без повторения

 combinationsStream(3, 2)
    .filter(xs -> Arrays.stream(xs).allMatch(x -> x < 2))
    ...
 

с выходом

 0, 0
0, 1
1, 0
1, 1
 

или с минимальными 3 элементами и максимальными 4 элементами

 combinationsStream(3, 2)
    .filter(xs -> { int sz = Arrays.stream(xs).sum(); return 3 <= sz amp;amp; sz <= 4; })
    ....
 

с выходом

 1, 2
2, 1
2, 2
3, 0
3, 1
 

и так далее.

Пример:

пусть у вас будут корзины с фруктами

 static class FruitBasket {
    String fruit;
    int quantity;
    FruitBasket(String fruit, int quantity) {
        this.fruit = fruit;
        this.quantity = quantity;
    }
}
 

и вы хотите приготовить фруктовый салат по крайней мере с 3 кусочками фруктов и не более чем с 4 и всегда по крайней мере с двумя разными фруктами с вашими доступными фруктами

 List<FruitBasket> elems = asList(
    new FruitBasket("apples",  5),
    new FruitBasket("oranges", 1),
    new FruitBasket("melons",  2));
 

затем

 combinationsStream(elems.stream()
        .mapToInt(FruitBasket::getQuantity) // quantity of each
        .map(n -> Math.min(2, n))           // max two of each
        .toArray())
    .filter(xs -> { int sz = Arrays.stream(xs).sum(); return 3 <= sz amp;amp; sz <= 4; })
    .forEach(xs -> System.out.println(
        IntStream.range(0, xs.length).mapToObj(i -> xs[i]   " "   elems.get(i).fruit).collect(joining(", "))));
 

с выходом

 0 apples, 1 oranges, 2 melons
1 apples, 0 oranges, 2 melons
1 apples, 1 oranges, 1 melons
1 apples, 1 oranges, 2 melons
2 apples, 0 oranges, 1 melons
2 apples, 0 oranges, 2 melons
2 apples, 1 oranges, 0 melons
2 apples, 1 oranges, 1 melons