Get all possible combination of items in array without duplicate groups in Swift

Question

I'm trying to create an extension on Array where I can get all possible combinations of an array without generating duplicate groups, including a no item combination.

For example, for this array:

[1, 2, 3, 4]

The following possible combinations should be generated:

[[], [1], [2], [3], [4], [1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4], [1, 2, 3], [1, 2, 4], [1, 3, 4], [2, 3, 4], [1, 2, 3, 4]]

Please note that none of the groups repeat themselves, i.e: if there is a group [1, 2] there is no other group: [2, 1].

This is the closest I've been able to get to a result:

public extension Array {

func allPossibleCombinations() -> [[Element]] {
    var output: [[Element]] = [[]]
    for groupSize in 1...self.count {
        for (index1, item1) in self.enumerated() {
            var group = [item1]
            for (index2, item2) in self.enumerated() {
                if group.count < groupSize {
                    if index2 > index1 {
                        group.append(item2)
                        if group.count == groupSize {
                            output.append(group)
                            group = [item1]
                            continue
                        }
                    }
                } else {
                    break
                }
            }
            if group.count == groupSize {
                output.append(group)
            }
        }
    }
    return output
}

}

But it is missing possible combination of items in the group size 3 (I only get back [1, 2, 3] and [2, 3, 4].

Much appreciated!

Maybe generate shuffled versions and apply the same method to each. This might help: https://stackoverflow.com/questions/127704/algorithm-to-return-all-combinations-of-k-elements-from-n — , May 10 '18 at 02:46

score 15 · Accepted Answer · edited Oct 15 '20 at 22:41

15

You can use flatMap also to combine them in one line.

extension Array {
    var combinationsWithoutRepetition: [[Element]] {
        guard !isEmpty else { return [[]] }
        return Array(self[1...]).combinationsWithoutRepetition.flatMap { [$0, [self[0]] + $0] }
    }
}
    
print([1,2,3,4].combinationsWithoutRepetition)

edited Oct 15 '20 at 22:41

Omer Faruk Ozturk

1,722
13
25

answered May 10 '18 at 05:19

Abdelahad Darwish

5,969
1
17
35

I prefer this answer because the results are returned in ascending order. – Danny Bravo May 14 '18 at 03:14

score 6 · Answer 2 · answered May 10 '18 at 02:53

6

extension Array {
    var combinations: [[Element]] {
        if count == 0 {
            return [self]
        }
        else {
            let tail = Array(self[1..<endIndex])
            let head = self[0]

            let first = tail.combinations
            let rest = first.map { $0 + [head] }

            return first + rest
        }
    }
}

print([1, 2, 3, 4].combinations)

answered May 10 '18 at 02:53

Nader

1,120
1
9
22

1

Thank you Nader, this is exactly what I needed! – Danny Bravo May 10 '18 at 03:05

score 4 · Answer 3 · 2022-03-03T09:42:29.950

4

This is in Algorithms now.

import Algorithms

Array([1, 2, 3, 4].combinations(ofCount: 0...))

edited Mar 03 '22 at 09:42

answered Mar 03 '22 at 09:36

Get all possible combination of items in array without duplicate groups in Swift

3 Answers3

Linked