How to to generate all possible k-element arrays from n-element array in Swift

Question

I want to create all possible k-element arrays from n-element array. k may be bigger or smaller than n. The elements in the output array don't have to be unique.

For example:

given this array

let a = [1,2]

the function given a desired size 3, should return :

[1,1,1]
[2,1,1]
[1,2,1]
[1,1,2]
[2,2,1]
[2,1,2]
[1,2,2]
[2,2,2]

example 2

given this array

let b = [[0,1], [2,3]]

the function given a desired size 3, should return :

[[0,1], [0,1], [0,1]]
[[2,3], [0,1], [0,1]]
[[0,1], [2,3], [0,1]]
[[0,1], [0,1], [2,3]]
[[2,3], [2,3], [0,1]]
[[2,3], [0,1], [2,3]]
[[0,1], [2,3], [2,3]]
[[2,3], [2,3], [2,3]]

How to do that in Swift?

Could you explain where the difference to stackoverflow.com/questions/25749941/… is, perhaps with a concrete example of given input and expected output? — Martin R
– Martin R, Commented Sep 17, 2014 at 18:36
here k maybe be bigger than n, and the elements in the output array don't have to be unique — ielyamani
– ielyamani, Commented Sep 17, 2014 at 18:38
A concrete example would still be helpful ... You could also show what you tried to far and where you are stuck. — Martin R
– Martin R, Commented Sep 17, 2014 at 18:40

Martin R · Accepted Answer · 2014-09-17 18:56:36Z

2

So you want all k-tuples with elements from a given set. This can be done recursively by taking all elements from the set as the first tuple element and combining that with all (k-1) tuples:

func allTupelsFrom<T>(elements: [T], withLength k : UInt,
    combinedWith prefix : [T] = []) -> [[T]] {

        if k == 0 {
            return [prefix]
        }

        var result : [[T]] = []
        for e in elements {
            result += allTupelsFrom(elements, withLength: k-1, combinedWith: prefix + [e])
        }
        return result
}

Examples:

let result1 = allTupelsFrom([1, 2], withLength: 3)
println(result1)
// [[1, 1, 1], [1, 1, 2], [1, 2, 1], [1, 2, 2], [2, 1, 1], [2, 1, 2], [2, 2, 1], [2, 2, 2]]

let result2 = allTupelsFrom(["a", "b", "c", "d"], withLength: 4)
println(result2)
// [[a, a, a, a], [a, a, a, b],  ... , [d, d, d, c], [d, d, d, d]]

answered Sep 17, 2014 at 18:56

Martin R

541k98 gold badges1.3k silver badges1.4k bronze badges

Sign up to request clarification or add additional context in comments.

8 Comments

ielyamani Over a year ago

How would the code change if elements were a an [[Int]]

Martin R Over a year ago

@Carpsen90: I have written it as a generic function so that it works with different types. The first example shows that it works with Int as well. If you don't want a generic function then you can remove the <T> in allTupelsFrom<T> and replace all T by Int inside the function.

ielyamani Over a year ago

I like this generic form, I am just trying to apply this function to an [[Int]] instead of an [Int], and I get an error on this line result += allTupelsFrom(elements, withLength: k-1, combinedWith: prefix + [e]) after changing elements to elements: [[T]]

Martin R Over a year ago

@Carpsen90: Sorry, I don't get it. What is the input array now? And what should the output be?

ielyamani Over a year ago

The input is [[Int]] not [Int] and the output is [[[Int]]] (all possible k-element arrays from the initial arrays)

|

Collectives™ on Stack Overflow

How to to generate all possible k-element arrays from n-element array in Swift

1 Answer 1

8 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

8 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related