Find all combination of string array in swift

Question

I have an Array of String and I want to find all the possible combinations of its element

For Example :

Array = [A,B,C,D]

should produce result as :

[A,AB,AC,AD,ABC,ABD,ACD,ABCD,B,BC,BD,BCD,C,CD,D]

Here is my Logic :

  var array = ["A", "B", "C","D"]
  var list = [String]()
  for i in 0..<array.count{
    let c = array[i]
    list.append(c)
    var d = c
    for count in 1..<array.count{

        if i+count < array.count{
            for j in i+count..<array.count{
                var a = d
                a.appendContentsOf(array[j])
                print("a : \(a)")
                list.append(a)
            }

        }
        d = c
        d.appendContentsOf(array[count])
        print("d : \(d)")
    }
}
print(list.description)

Its Output is :

["A", "AB", "AC", "AD", "ABC", "ABD", "ACD", "B", "BC", "BD", "BBD", "C", "CD", "D"]

This output is missing ABCD and wrongly printed BCD as BBD

Anyone Please Help me in this by Enhancing my code or suggesting your own logic for this.

Mudlark

#33021564 – Passed

i have already searched it before ,the problem in this link was of permutation not combination (i want just ABCD not ABCD , ACBD ...) – Mudlark

Your result repeats e.g. B and C. I don't think this is intended? – Urbanite

ohh yes it was a Typo.. M editing my question.. Thanks – Mudlark

Answer 1

@yannick's answer is very close.

By computing a Power Set of your set, you obtain all the possible subsets (including your original set and the empty set).

Once you have obtained the Power Set, all you have to do is join the subsets into a single string in order to obtain the result that you're looking for.

Here's the complete solution (along with updated code and plenty of comments):

extension Array {
    var powerset: [[Element]] {
        guard count > 0 else {
            return [[]]
        }

        // tail contains the whole array BUT the first element
        let tail = Array(self[1..<endIndex])

        // head contains only the first element
        let head = self[0]

        // computing the tail's powerset
        let withoutHead = tail.powerset

        // mergin the head with the tail's powerset
        let withHead = withoutHead.map { $0 + [head] }

        // returning the tail's powerset and the just computed withHead array
        return withHead + withoutHead
    }
}

let myArray = ["A", "B", "C", "D"]
print(myArray.powerset) // -> [["D", "C", "B", "A"], ["C", "B", "A"], ["D", "B", "A"], ["B", "A"], ["D", "C", "A"], ["C", "A"], ["D", "A"], ["A"], ["D", "C", "B"], ["C", "B"], ["D", "B"], ["B"], ["D", "C"], ["C"], ["D"], []]

// joining the subsets
let myResult = myArray.powerset.map { $0.sort().joinWithSeparator("") }
print(myResult) // -> ["A", "AB", "ABC", "ABCD", "ABD", "AC", "ACD", "AD", "B", "BC", "BCD", "BD", "C", "CD", "D", ""]

PS

Note that this solution uses a recursive approach, while yours was using an iterative approach.

PPS

If you don't want the empty string "" in your solution, you can just filter it away:

let myResult = myArray.powerset.map({ $0.sort().joinWithSeparator("") }).filter({ $0 != "" })

print(myResult) // -> ["A", "AB", "ABC", "ABCD", "ABD", "AC", "ACD", "AD", "B", "BC", "BCD", "BD", "C", "CD", "D"]

Moulder

Perfect!! . That's what i actually wanted – Mudlark

but the output is in reverse order i.e (instead of DCBA , it should be ABCD) for that i changed the lastline a little let myResult = array.powerset.map({ $0.reverse().joinWithSeparator("/") }).filter({ $0 != "" }) – Mudlark

That's interesting, I'm using the IBM Swift simulator ( swiftlang.ng.bluemix.net ) and whether I use sort or reverse the outcome is exactly the same! Either way, I'm happy you got your solution :) – Moulder

what is the complexity of this solution it happens to have a limit of number of items on 38 items it is too large for it – Shaum

Answer 2

It looks like you want to have the Power set of your array.

In mathematics, the power set (or powerset) of any set S is the set of all subsets of S, including the empty set and S itself.

I found this Code on GitHub.

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

            let withoutHead = tail.powerset
            let withHead = withoutHead.map { $0 + [head] }

            return withHead + withoutHead
        }
    }
}

println([1,2,3,4].powerset) -> [[4, 3, 2, 1], [3, 2, 1], [4, 2, 1], [2, 1], [4, 3, 1], [3, 1], [4, 1], [1], [4, 3, 2], [3, 2], [4, 2], [2], [4, 3], [3], [4], []]

Urbanite

What should this be other than swift? – Urbanite

ohh sorry ,yes it is in swift but can i get its explanation because am not able to change it – Mudlark

Try running it and insert some prints. This should give you a good understanding – Urbanite

Answer 3

I find a neater answer for it.Power set of Collection.

The principle is using induction on the size of a collection, as showed on that link. Here is the copy of code from that link. And all credits to its author.

extension Collection {
  public var powerSet: [[Element]] {
    guard let fisrt = self.first else {return [[]]}
    return self.dropFirst().powerSet.flatMap{[$0, [fisrt] + $0]}
  }
}
let s: Set<Int> = [1,2,3]
s.powerSet //[[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]
let a: Array<Int> = [1,2,3]
a.powerSet //[[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]

Quirinus

Answer 4

I know some good answers have been given already, but coming from a Java background, I just wanted to drop some insights using bitwise operators (which surprisingly still work in Swift).

You can try this out:

let len = stringArr.count

for i in 0 ..< (1<<len){
    print("{", terminator: "")

    for j in 0 ..< len {
        if ((i & (1<<j)) > 0) {
            print(stringArr[j], terminator: "")
        }
    }

    print("}")
}

You can find more information on bitwise operators here

Fixing

Answer 5

I will take a shot also using this logic as reference:

extension RangeReplaceableCollection {
    var subSets : [SubSequence] {
        guard !isEmpty else { return [] }
        let count = self.count
        let n = 1 << count - 1
        var subSequences: [SubSequence] = .init(repeating: SubSequence(), count: n-1)
        (0 ..< n).forEach { x in
            autoreleasepool {
                var counter = 0
                for element in self {
                    if x & 1 << counter > 0 {
                        subSequences[x-1].append(element)
                    }
                    counter += 1
                }
            }

        }
        return subSequences + [self[...]]
    }
}

---

Playground Testing:

["A", "B", "C","D"].subSets  // [["A"], ["B"], ["A", "B"], ["C"], ["A", "C"], ["B", "C"], ["A", "B", "C"], ["D"], ["A", "D"], ["B", "D"], ["A", "B", "D"], ["C", "D"], ["A", "C", "D"], ["B", "C", "D"], ["A", "B", "C", "D"]]

"ABCD".subSets  // ["A", "B", "AB", "C", "AC", "BC", "ABC", "D", "AD", "BD", "ABD", "CD", "ACD", "BCD", "ABCD"]

Betweentimes

what is max count of input array? it seems to be allocating too large block of memory on [SubSequance] – Shaum

@MichałZiobro check my last method. Let me know if that fixed the memory issue – Betweentimes

If that is not enough I can add another one inside the inner loop. for element in self { autoreleasepool { – Betweentimes

I think it crashes here and cannot allocate memory for this array .init(repeating: SubSequence(), count: n-1) as n is huge (1 << 37 ) – Shaum

kkkk Thats way too much subsequences. What is your input? – Betweentimes

I've used combinatorics library and combinations k-elements from N. As I need only subsets of size 1,2,3 elements. So I've taken subsets of cardinality 1,2,3 and each is combinations of 1-elements, 2-elements, 3-elements from N – Shaum

Input is random this are names read from business card it can be 10 or 20 or 40 names. It crashes in recursive or this iterative approach on 37 elements array – Shaum

I think the only way to avoid that is to dump it to disk instead of to memory. Anyway it will take a long time to complete that task. – Betweentimes