Подтвердить что ты не робот

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

Я работаю над головоломкой, которая включает в себя анализ всех подмножеств 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 размера?

EDIT: я, наконец, получил эту функцию, мне пришлось создать новую переменную, которая была такой же, как я, чтобы выполнить сравнение я и thresh, потому что python обрабатывает индексы цикла по-разному.

4b9b3361

ОТВЕТЫ

Ответ 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);
}

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

Ответ 2

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

Пример:

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]

Ответ 3

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

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

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

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 миллисекундах.

Ответ 4

Вдохновленный afsantos ответом: -)... Я решил написать реализацию С#.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 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;
}

Ответ 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("}");
     }
    }

Ответ 6

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

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

}

Ответ 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
}