Funkcja zwracająca tablicę tablic wszystkich n-elementowych kombinacji tablicy x

Question

Przykładowo:

Wszystkie 4-elemntowe kombinacje z tablicy {1,2,3,4,5} = {1,2,3,4}, {1,2,3,5}, {1,2,5,4}, {1,5,3,4}, {5,2,3,4}

Kolejność jest bez znaczenia oraz mogę zagwarantować, że żaden element się nie powtórzy.

Wiem jak policzyć ilość elementów, ale w obliczeniach pojawiają się silnie, więc zakładam, że będzie problem z pamięcią przy tablicach powyżej 15 elementów, ale nie ma to dla mnie zbyt dużego znaczenia.

Jak wyglądałby algorytm(wszystko jedno w jakim języku) który by się z tym uporał?

Comments

kombinacje z tablicy 5 elementowej do tablic 4 elementowych czy ogółem.

Answer 1

Dla inspiracji....

Z premedytacją rozwiązanie bazujące na strukturze zbioru więc da się to zrobić jeszcze wydajniej :-) Warto zerknąć do <algorithm>. Podpowiadam że tam jest kilka algorytmów które może Ci pomóc :-)

#include <iostream>
#include <algorithm>
#include <vector>
#include <iterator>
#include <set>

using namespace std;

using values_t = vector<int>;
using combinations_t = set<values_t>;

void showCombinations(const combinations_t& combinations) {
    for(const auto& combination: combinations) {
        auto cend = prev(combination.cend());
        copy(combination.cbegin(), cend, ostream_iterator<int>(cout, ", "));
        cout << *(combination.rbegin()) << endl;
    }
}

combinations_t generateCombinations(values_t& values, size_t n) {
    combinations_t combinations;
    do {
        combinations.insert(values_t(values.cbegin(), values.cbegin() + n));
    } while(next_permutation(values.begin(), values.end()));
    return combinations;
}

int main() {

    values_t vec = {1,2,3,4};

    combinations_t combinations = generateCombinations(vec, 3);

    showCombinations(combinations);
}

 

Answer 2

Najłatwiejszy sposób jaki mi przyszedł do głowy tak na szybko. 

func combinationWithoutRepetition(array: [Int], subsetNumberOfElements: Int) -> [[Int]] {
    let combination = combinationWithRepetition(array: array, subsetNumberOfElements: subsetNumberOfElements)
    
    let combitationWithoutRepetition = combination.filter { subset in
        let uniqueElementsSubset = Set(subset)
        return uniqueElementsSubset.count == subset.count
    }
    
    return combitationWithoutRepetition
}

func combinationWithRepetition(array: [Int], subsetNumberOfElements: Int) -> [[Int]] {
    var array = array
    
    guard subsetNumberOfElements > 0 else {
        return [[]]
    }
    
    guard array.isEmpty == false else {
        return []
    }
    
    let head = [array[0]]
    let subCombitation = combinationWithRepetition(array: array, subsetNumberOfElements: subsetNumberOfElements - 1)
    var combination = subCombitation.map {head + $0}
    array.remove(at: 0)
    combination += combinationWithRepetition(array: array, subsetNumberOfElements: subsetNumberOfElements)
    return combination
}