Как сгенерировать только 3 раздела списка целых чисел

Question

Я ищу помощь в адаптации кода Java, который генерирует все разделы из набора целых чисел.Я хочу изменить код (который я нашел в Stackoverflow), чтобы генерировать только разделы из 3 подмножеств.

Пример:

В моем списке содержится 1, 2, 3, 4, 5, 6

Я хочу получить разделы по 3, т.е. я хочу разбить свой список на 3 подмножества.

Вывод должен выглядеть следующим образом:

[1, 2, 3], [4], [5, 6]

[1, 2], [3, 5], [4, 6]

и т. Д. *

Я пыталсяизменить этот код напрасно.Если я сгенерирую все разделы, то рассмотрим только те, которые разделены на 3 подсписка.Это стоит времени.Поэтому я стараюсь не создавать ненужные разделы.

Ссылка на код:

Получить все возможные разделы набора

package PartitionSetCreator;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Set;

public class PartitionSetCreator<T> {

    private Set<Set<Set<T>>> parts;//the partitions that are created
    private Set<Set<T>> pow;//the power set of the input set
    private Set<T> base;//the base set

    /**
     * The main method is just for testing and can be deleted.
     */
    public static void main(String[] args) {
        //test using an empty set = []
        Set<Integer> baseSet = new HashSet<Integer>();

        for (int i = 1; i < 10; i++) {
            baseSet.add(i);
        }
        System.out.println("BaseSet: " + baseSet);
        PartitionSetCreator<Integer> partSetCreator5 = new PartitionSetCreator<Integer>(baseSet);
        Set<Set<Set<Integer>>> partitionSets5 = partSetCreator5.findAllPartitions();
        System.out.println("Result:  " + partitionSets5);

        Iterator<Set<Set<Integer>>> iter = partitionSets5.iterator();
        Set<Set<Set<Integer>>> partitionSetsof3 = new HashSet<Set<Set<Integer>>>();

        //Print the output
        for (Set<Set<Integer>> stock : partitionSets5) {
            //Extract when the size is equal to 3
            if (stock.size() == 3) {
                partitionSetsof3.add(stock);
                System.out.println(stock);
            }
        }
        System.out.println(partitionSetsof3);

        System.out.println("Base-Size: " + baseSet.size() + " Result-Size: " + partitionSets5.size());

    }

    public PartitionSetCreator(Set<T> base) {
        this.base = base;
        this.pow = powerSet(base);
        if (pow.size() > 1) {
            //remove the empty set if it's not the only entry in the power set
            pow.remove(new HashSet<T>());
        }
        this.parts = new HashSet<Set<Set<T>>>();
    }

    /**
     * Calculation is in this method.
     */
    public Set<Set<Set<T>>> findAllPartitions() {
        //find part sets for every entry in the power set
        for (Set<T> set : pow) {
            Set<Set<T>> current = new HashSet<Set<T>>();
            current.add(set);
            findPartSets(current);
        }

        //return all partitions that were found
        return parts;
    }

    /**
     * Finds all partition sets for the given input and adds them to parts (global variable).
     */
    private void findPartSets(Set<Set<T>> current) {
        int maxLen = base.size() - deepSize(current);
        if (maxLen == 0) {
            //the current partition is full -> add it to parts
            parts.add(current);
            //no more can be added to current -> stop the recursion
            return;
        } else {
            //for all possible lengths
            for (int i = 1; i <= maxLen; i++) {
                //for every entry in the power set
                for (Set<T> set : pow) {
                    if (set.size() == i) {
                        //the set from the power set has the searched length
                        if (!anyInDeepSet(set, current)) {
                            //none of set is in current
                            Set<Set<T>> next = new HashSet<Set<T>>();
                            next.addAll(current);
                            next.add(set);
                            //next = current + set
                            findPartSets(next);
                        }
                    }
                }
            }
        }
    }

    /**
     * Creates a power set from the base set.
     */
    private Set<Set<T>> powerSet(Set<T> base) {
        Set<Set<T>> pset = new HashSet<Set<T>>();
        if (base.isEmpty()) {
            pset.add(new HashSet<T>());
            return pset;
        }
        List<T> list = new ArrayList<T>(base);
        T head = list.get(0);
        Set<T> rest = new HashSet<T>(list.subList(1, list.size()));
        for (Set<T> set : powerSet(rest)) {
            Set<T> newSet = new HashSet<T>();
            newSet.add(head);
            newSet.addAll(set);
            pset.add(newSet);
            pset.add(set);
        }

        return pset;
    }

    /**
     * The summed up size of all sub-sets
     */
    private int deepSize(Set<Set<T>> set) {
        int deepSize = 0;
        for (Set<T> s : set) {
            deepSize += s.size();
        }
        return deepSize;
    }

    /**
     * Checks whether any of set is in any of the sub-sets of current
     */
    private boolean anyInDeepSet(Set<T> set, Set<Set<T>> current) {
        boolean containing = false;

        for (Set<T> s : current) {
            for (T item : set) {
                containing |= s.contains(item);
            }
        }

        return containing;
    }
}

Ожидается, что избежать создания ненужных разделов для ускорениябежать.

Answer 1

Используйте Arrays.copyOfRange

static void splitArray(int[] arr) {
    int i, j, k;
    int n = arr.length;
    for (i = 1; i < n; i++) {
        for (j = 1; j < n; j++) {
            for (k = 1; k < n; k++) {
                if (i + j + k == n) {
                    System.out.println( //
                        Arrays.toString(Arrays.copyOfRange(arr, 0, i)) + ", " + //
                        Arrays.toString(Arrays.copyOfRange(arr, i, i + j)) + ", " + //
                        Arrays.toString(Arrays.copyOfRange(arr, i + j, n)) //
                    );
                }
            }
        }
    }
}

public static void main(String[] args) {
    int[] arr = { 1, 2, 3, 4, 5, 6 };
    splitArray(arr);
}

Ouput

[1], [2], [3, 4, 5, 6]
[1], [2, 3], [4, 5, 6]
[1], [2, 3, 4], [5, 6]
[1], [2, 3, 4, 5], [6]
[1, 2], [3], [4, 5, 6]
[1, 2], [3, 4], [5, 6]
[1, 2], [3, 4, 5], [6]
[1, 2, 3], [4], [5, 6]
[1, 2, 3], [4, 5], [6]
[1, 2, 3, 4], [5], [6]

В общем случае используйте CollectionUtils.permutations , чтобы найти всеперестановки arr и вызов splitArray() для каждой перестановки