1
\$\begingroup\$

I want to generate all the subarrays from an array of integer as below:

func subarrays(_ arr: [Int]) -> [[Int]]{
    var result = [[Int]]()
    guard arr.count >= 1 else { return [arr] }
    for i in 0..<arr.count {
        for res in result {
            var resi = res
            resi.append(arr[i])
            result.append(resi)
        }

        result.append([ arr[i] ])
    }
    result.append([])
    return result
}

subarrays([1,2]) //{},{1,2},{1},{2}
subarrays([1,2,3]) //{} {1}{2}{3}{1,2}{2,3}{1,3}{1,2,3}

I have alternative implementations, but really want to know if it is acceptable to use

for res in result

while adding to the array, or whether this would be seen as unusual practice in any way.

\$\endgroup\$
1
\$\begingroup\$

To answer your immediate question: Yes, it is fine to mutate an array while enumerating its elements. The reason is that

for res in result { ... }

is equivalent to

var iter = result.makeIterator()
while let res = iter.next() {
    // ...
}

and that arrays are value types in Swift: Mutating result inside the loop creates a new value and does not affect the original array that the iterator is using. See Remove element from collection during iteration with forEach on Stack Overflow for more details.

There are some possible simplifications. Here

var resi = res
resi.append(arr[i])
result.append(resi)

is is not necessary to declare another array variable, this can be shortened to

result.append(res + [arr[i]])

A better name for the res variable might be subarray or subset.

Instead of looping over the array indices

for i in 0..<arr.count {
    // ... do something with `arr[i]` ...
}

you can enumerate the array (as you already do in the inner loop)

for elem in arr {
    // ... do something with `elem` ...
}

The

guard arr.count >= 1 else { return [arr] }

is not needed. Your algorithm already does “the right thing” for an empty array.

So this is what we have so far:

func subarrays(_ arr: [Int]) -> [[Int]] {
    var result = [[Int]]()
    for elem in arr {
        for subarray in result {
            result.append(subarray + [elem])
        }
        result.append([elem])
    }
    result.append([])
    return result
}

It becomes a bit simpler if result is not initialized with an empty list, but with a list containing the empty subset. Adding the array element itself, and the empty set at the end of the function is no longer necessary:

func subarrays(_ arr: [Int]) -> [[Int]] {
    var result: [[Int]] = [[]]
    for elem in arr {
        for subarray in result {
            result.append(subarray + [elem])
        }
    }
    return result
}

(The subset are returned in a different order now, though.)

The inner loop could be replaced by a map operation:

func subarrays(_ arr: [Int]) -> [[Int]] {
    var result: [[Int]] = [[]]
    for elem in arr {
        result.append(contentsOf: result.map { $0 + [elem] })
    }
    return result
}

or even the entire function body replaced by a single expression:

func subarrays(_ arr: [Int]) -> [[Int]] {
    return arr.reduce(into: [[]], { (result, elem) in
        result.append(contentsOf: result.map { $0 + [elem] })
    })
}

but that is a matter of taste – is not necessarily easier to read.

There is nothing particular with respect to integers in the algorithm, the function can be made generic to take arrays of any element type – or even arbitrary sequences.

Finally I would call it subsets(of:), which is what the function computes:

func subsets<S: Sequence>(of seq: S) -> [[S.Element]] {
    var result: [[S.Element]] = [[]]
    for elem in seq {
        for subset in result {
            result.append(subset + [elem])
        }
    }
    return result
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.