Как итеративно генерировать k подмножеств элементов из набора размера n в Java?

Question

Я работаю над головоломкой, которая включает анализ всех подмножеств размера k и выяснение, какое из них оптимально.Я написал решение, которое работает, когда число подмножеств мало, но ему не хватает памяти для больших проблем.Теперь я пытаюсь перевести итеративную функцию, написанную на python, в java, чтобы я мог анализировать каждое подмножество по мере его создания и получать только значение, представляющее, насколько оно оптимизировано, а не весь набор, чтобы у меня не кончилисьобъем памяти.Вот то, что у меня есть до сих пор, и кажется, что оно не заканчивается даже для очень маленьких проблем:

public static LinkedList<LinkedList<Integer>> getSets(int k, LinkedList<Integer> set)
{
    int N = set.size();
    int maxsets = nCr(N, k);
    LinkedList<LinkedList<Integer>> toRet = new LinkedList<LinkedList<Integer>>();

    int remains, thresh;
    LinkedList<Integer> newset; 
    for (int i=0; i<maxsets; i++)
    {
        remains = k;
        newset = new LinkedList<Integer>();
        for (int val=1; val<=N; val++)
        {
            if (remains==0)
                break;
            thresh = nCr(N-val, remains-1);
            if (i < thresh)
            {
                newset.add(set.get(val-1));
                remains --;
            }
            else 
            {
                i -= thresh;
            }
        }
        toRet.add(newset);
    }

    return toRet;

}

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

РЕДАКТИРОВАТЬ: я наконец-то получил эту функцию, мне пришлось создать новую переменную, которая была такой же, как я, чтобы сделать сравнение i и thresh, потому что python по-разному обрабатывает индексы цикла.

Answer 1

Во-первых, если вы собираетесь использовать произвольный доступ к списку, вы должны выбрать реализацию списка, которая эффективно это поддерживает. Из Javadoc на LinkedList:

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

ArrayList более экономичен и намного быстрее для произвольного доступа. На самом деле, поскольку вы заранее знаете длину, вы можете даже использовать простой массив.

Алгоритмам: давайте начнем с простого: как бы вы сгенерировали все подмножества размера 1? Вероятно, так:

for (int i = 0; i < set.length; i++) {
    int[] subset = {i};
    process(subset);
}

Где процесс - это метод, который делает что-то с набором, например, проверяет, является ли он "лучше", чем все подмножества, обработанные до сих пор.

Теперь, как бы вы расширили это для работы с подмножествами размера 2? Какова взаимосвязь между подмножествами размера 2 и подмножествами размера 1? Ну, любое подмножество размера 2 можно превратить в подмножество размера 1, удалив его самый большой элемент. Иными словами, каждое подмножество размера 2 можно сгенерировать, взяв подмножество размера 1 и добавив новый элемент, больший, чем все другие элементы в наборе. В коде:

processSubset(int[] set) {
    int subset = new int[2];
    for (int i = 0; i < set.length; i++) {
        subset[0] = set[i];
        processLargerSets(set, subset, i);
    }
}

void processLargerSets(int[] set, int[] subset, int i) {
    for (int j = i + 1; j < set.length; j++) {
        subset[1] = set[j];
        process(subset);
    }
}

Для подмножеств произвольного размера k обратите внимание, что любое подмножество размера k можно превратить в подмножество размера k-1 путем измельчения самого большого элемента. То есть все подмножества размера k могут быть сгенерированы путем генерации всех подмножеств размера k-1, и для каждого из них и каждого значения, большего, чем наибольшее в подмножестве, добавьте это значение к набору. В коде:

static void processSubsets(int[] set, int k) {
    int[] subset = new int[k];
    processLargerSubsets(set, subset, 0, 0);
}

static void processLargerSubsets(int[] set, int[] subset, int subsetSize, int nextIndex) {
    if (subsetSize == subset.length) {
        process(subset);
    } else {
        for (int j = nextIndex; j < set.length; j++) {
            subset[subsetSize] = set[j];
            processLargerSubsets(set, subset, subsetSize + 1, j + 1);
        }
    }
}

Тестовый код:

static void process(int[] subset) {
    System.out.println(Arrays.toString(subset));
}


public static void main(String[] args) throws Exception {
    int[] set = {1,2,3,4,5};
    processSubsets(set, 3);
}

Но прежде чем вызывать это на больших наборах, помните, что число подмножеств может расти довольно быстро.

Answer 2

Вы можете использовать org.apache.commons.math3.util.Combination .

Пример:

import java.util.Arrays;
import java.util.Iterator;

import org.apache.commons.math3.util.Combinations;

public class tmp {
    public static void main(String[] args) {
        for (Iterator<int[]> iter = new Combinations(5, 3).iterator(); iter.hasNext();) {
            System.out.println(Arrays.toString(iter.next()));
        }
    }

}

Вывод: [0, 1, 2][0, 1, 3] [0, 2, 3] [1, 2, 3] [0, 1, 4] [0, 2, 4] [1, 2, 4] [0, 3, 4] [1, 3, 4] [2, 3, 4]

Answer 3

У меня была та же проблема сегодня, когда я генерировал все k-размера подмножества n-размера .

У меня был рекурсивный алгоритм,написано на Haskell, но проблема требовала, чтобы я написал новую версию на Java.В Java я подумал, что мне, вероятно, придется использовать памятку для оптимизации рекурсии.Оказывается, я нашел способ сделать это итеративно.Я был вдохновлен этим изображением из Википедии, на статье о комбинациях.

Метод для вычисления всех k-size подмножеств :

public static int[][] combinations(int k, int[] set) {
    // binomial(N, K)
    int c = (int) binomial(set.length, k);
    // where all sets are stored
    int[][] res = new int[c][Math.max(0, k)];
    // the k indexes (from set) where the red squares are
    // see image above
    int[] ind = k < 0 ? null : new int[k];
    // initialize red squares
    for (int i = 0; i < k; ++i) { ind[i] = i; }
    // for every combination
    for (int i = 0; i < c; ++i) {
        // get its elements (red square indexes)
        for (int j = 0; j < k; ++j) {
            res[i][j] = set[ind[j]];
        }
        // update red squares, starting by the last
        int x = ind.length - 1;
        boolean loop;
        do {
            loop = false;
            // move to next
            ind[x] = ind[x] + 1;
            // if crossing boundaries, move previous
            if (ind[x] > set.length - (k - x)) {
                --x;
                loop = x >= 0;
            } else {
                // update every following square
                for (int x1 = x + 1; x1 < ind.length; ++x1) {
                    ind[x1] = ind[x1 - 1] + 1;
                }
            }
        } while (loop);
    }
    return res;
}

Метод бинома: (Адаптировано из примера Python, из Википедии)

private static long binomial(int n, int k) {
    if (k < 0 || k > n) return 0;
    if (k > n - k) {    // take advantage of symmetry
        k = n - k;
    }
    long c = 1;
    for (int i = 1; i < k+1; ++i) {
        c = c * (n - (k - i));
        c = c / i;
    }
    return c;
}

Конечно, комбинации всегда будут иметь проблему с пространством, так как они, вероятно, взрываются.В контексте моей собственной проблемы, максимально возможное значение составляет около 2 000 000 подмножеств.Моя машина рассчитала это за 1032 миллисекунды.

Answer 4

Вот итератор комбинации, который я написал недавно

package psychicpoker;

import java.util.ArrayList;
import java.util.Collection;
import java.util.Iterator;
import java.util.List;

import static com.google.common.base.Preconditions.checkArgument;

public class CombinationIterator<T> implements Iterator<Collection<T>> {

private int[] indices;
private List<T> elements;
private boolean hasNext = true;

public CombinationIterator(List<T> elements, int k) throws IllegalArgumentException {
    checkArgument(k<=elements.size(), "Impossible to select %d elements from hand of size %d", k, elements.size());
    this.indices = new int[k];
    for(int i=0; i<k; i++)
        indices[i] = k-1-i;
    this.elements = elements;
}

public boolean hasNext() {
    return hasNext;
}

private int inc(int[] indices, int maxIndex, int depth) throws IllegalStateException {
    if(depth == indices.length) {
        throw new IllegalStateException("The End");
    }
    if(indices[depth] < maxIndex) {
        indices[depth] = indices[depth]+1;
    } else {
        indices[depth] = inc(indices, maxIndex-1, depth+1)+1;
    }
    return indices[depth];
}

private boolean inc() {
    try {
        inc(indices, elements.size() - 1, 0);
        return true;
    } catch (IllegalStateException e) {
        return false;
    }
}

public Collection<T> next() {
    Collection<T> result = new ArrayList<T>(indices.length);
    for(int i=indices.length-1; i>=0; i--) {
        result.add(elements.get(indices[i]));
    }
    hasNext = inc();
    return result;
}

public void remove() {
    throw new UnsupportedOperationException();
}

}

Answer 5

Это решение у меня сработало:

 private static void findSubsets(int array[])
    {
      int numOfSubsets = 1 << array.length; 

      for(int i = 0; i < numOfSubsets; i++)
     {
        int pos = array.length - 1;
       int bitmask = i;

       System.out.print("{");
       while(bitmask > 0)
       {
        if((bitmask & 1) == 1)
         System.out.print(array[pos]+",");
        bitmask >>= 1;
        pos--;
       }
       System.out.print("}");
     }
    }

Answer 6

Вдохновленный ответом afsantos: -) ... Я решил написать реализацию C # .NET для генерации всех комбинаций подмножеств определенного размера из полного набора. Не нужно рассчитывать общее количество возможных подмножеств; он обнаруживает, когда он достиг конца. Вот оно:

public static List<object[]> generateAllSubsetCombinations(object[] fullSet, ulong subsetSize) {
    if (fullSet == null) {
        throw new ArgumentException("Value cannot be null.", "fullSet");
    }
    else if (subsetSize < 1) {
        throw new ArgumentException("Subset size must be 1 or greater.", "subsetSize");
    }
    else if ((ulong)fullSet.LongLength < subsetSize) {
        throw new ArgumentException("Subset size cannot be greater than the total number of entries in the full set.", "subsetSize");
    }

    // All possible subsets will be stored here
    List<object[]> allSubsets = new List<object[]>();

    // Initialize current pick; will always be the leftmost consecutive x where x is subset size
    ulong[] currentPick = new ulong[subsetSize];
    for (ulong i = 0; i < subsetSize; i++) {
        currentPick[i] = i;
    }

    while (true) {
        // Add this subset's values to list of all subsets based on current pick
        object[] subset = new object[subsetSize];
        for (ulong i = 0; i < subsetSize; i++) {
            subset[i] = fullSet[currentPick[i]];
        }
        allSubsets.Add(subset);

        if (currentPick[0] + subsetSize >= (ulong)fullSet.LongLength) {
            // Last pick must have been the final 3; end of subset generation
            break;
        }

        // Update current pick for next subset
        ulong shiftAfter = (ulong)currentPick.LongLength - 1;
        bool loop;
        do {
            loop = false;

            // Move current picker right
            currentPick[shiftAfter]++;

            // If we've gotten to the end of the full set, move left one picker
            if (currentPick[shiftAfter] > (ulong)fullSet.LongLength - (subsetSize - shiftAfter)) {
                if (shiftAfter > 0) {
                    shiftAfter--;
                    loop = true;
                }
            }
            else {
                // Update pickers to be consecutive
                for (ulong i = shiftAfter+1; i < (ulong)currentPick.LongLength; i++) {
                    currentPick[i] = currentPick[i-1] + 1;
                }
            }
        } while (loop);
    }

    return allSubsets;
}

Answer 7

Быстрая реализация:

Ниже приведены два варианта ответа, предоставленного afsantos .

Первая реализация функции combinations отражает функциональные возможности исходной реализации Java.

Вторая реализация является общим случаем для нахождения всех комбинаций значений k из набора [0, setSize). Если это действительно все, что вам нужно, эта реализация будет более эффективной.

Кроме того, они включают несколько незначительных оптимизаций и упрощенную логику smidgin.

/// Calculate the binomial for a set with a subset size
func binomial(setSize: Int, subsetSize: Int) -> Int
{
    if (subsetSize <= 0 || subsetSize > setSize) { return 0 }

    // Take advantage of symmetry
    var subsetSizeDelta = subsetSize
    if (subsetSizeDelta > setSize - subsetSizeDelta)
    {
        subsetSizeDelta = setSize - subsetSizeDelta
    }

    // Early-out
    if subsetSizeDelta == 0 { return 1 }

    var c = 1
    for i in 1...subsetSizeDelta
    {
        c = c * (setSize - (subsetSizeDelta - i))
        c = c / i
    }
    return c
}

/// Calculates all possible combinations of subsets of `subsetSize` values within `set`
func combinations(subsetSize: Int, set: [Int]) -> [[Int]]?
{
    // Validate inputs
    if subsetSize <= 0 || subsetSize > set.count { return nil }

    // Use a binomial to calculate total possible combinations
    let comboCount = binomial(setSize: set.count, subsetSize: subsetSize)
    if comboCount == 0 { return nil }

    // Our set of combinations
    var combos = [[Int]]()
    combos.reserveCapacity(comboCount)

    // Initialize the combination to the first group of set indices
    var subsetIndices = [Int](0..<subsetSize)

    // For every combination
    for _ in 0..<comboCount
    {
        // Add the new combination
        var comboArr = [Int]()
        comboArr.reserveCapacity(subsetSize)
        for j in subsetIndices { comboArr.append(set[j]) }
        combos.append(comboArr)

        // Update combination, starting with the last
        var x = subsetSize - 1
        while true
        {
            // Move to next
            subsetIndices[x] = subsetIndices[x] + 1

            // If crossing boundaries, move previous
            if (subsetIndices[x] > set.count - (subsetSize - x))
            {
                x -= 1
                if x >= 0 { continue }
            }
            else
            {
                for x1 in x+1..<subsetSize
                {
                    subsetIndices[x1] = subsetIndices[x1 - 1] + 1
                }
            }
            break
        }
    }
    return combos
}


/// Calculates all possible combinations of subsets of `subsetSize` values within a set
/// of zero-based values for the set [0, `setSize`)
func combinations(subsetSize: Int, setSize: Int) -> [[Int]]?
{
    // Validate inputs
    if subsetSize <= 0 || subsetSize > setSize { return nil }

    // Use a binomial to calculate total possible combinations
    let comboCount = binomial(setSize: setSize, subsetSize: subsetSize)
    if comboCount == 0 { return nil }

    // Our set of combinations
    var combos = [[Int]]()
    combos.reserveCapacity(comboCount)

    // Initialize the combination to the first group of elements
    var subsetValues = [Int](0..<subsetSize)

    // For every combination
    for _ in 0..<comboCount
    {
        // Add the new combination
        combos.append([Int](subsetValues))

        // Update combination, starting with the last
        var x = subsetSize - 1
        while true
        {
            // Move to next
            subsetValues[x] = subsetValues[x] + 1

            // If crossing boundaries, move previous
            if (subsetValues[x] > setSize - (subsetSize - x))
            {
                x -= 1
                if x >= 0 { continue }
            }
            else
            {
                for x1 in x+1..<subsetSize
                {
                    subsetValues[x1] = subsetValues[x1 - 1] + 1
                }
            }
            break
        }
    }
    return combos
}