Alternate ways to create combinations of a range of numbers

Using Swift
,
1

Hello Swift crew!

This is my first post. I'm on a self-learning journey with Swift. I'm working my way through Stanford's latest iOS course that's available publicly.

As an exercise, I'm going to complete an assignment that creates a game of Solo Set.

I've come up with a way to represent each card (81 in total) using integers from 0...2.

I've even managed to generate all the cards with these combinations using iteration.

let variations = 0...2

var cards:[[Int]] = []

for shape in variations {
    for shading in variations {
        for colour in variations {
            for numItems in variations {
                cards.append([shape, shading, colour, numItems])
            }
        }
    }
}

cards.forEach { print("\($0)") }

"""
Outputs:
[0, 0, 0, 0]
[0, 0, 0, 1]
...
[2, 2, 2, 2]
"""

But I don't have a computer science background thus no experience in algorithms or recursion — it's something I want to rectify.

I suspect there is a better way to achieve what I'm achieving through either an algorithm or recursion.

I checked out this WWDC video on the Swift Algorithms and Collections packages. I suspect I could use combinations or permutations, but I haven't been able to crack it.

Those in the know, would you be able to nudge me in the right direction using an algorithm or recursion? I would like to build my understanding and would love any hints or tips to help move me along.

Thanks for considering my post :slight_smile:

3 Likes
2

Algorithms: If you like reading, you can start your journey in the world of algorithms with this book from the MIT Press: Introduction to Algorithms.

Recursion is good for solving problems by using the divide and conquer strategy.

Here is a program using recursion to compute the sum of integers from 1 to N.


struct Algo1 {
    static func sum (to N: UInt) -> UInt {
        if N <= 1 {
            return N
        }
        else {
            return N + sum (to: N - 1)
        }
        
        // sum = N + (N-1 + N-2 ... + 1)
    }
}

struct Algo2 {
    static func sum (to N: UInt) -> UInt {
        return (N * (N + 1)) / 2
        
        // sum = 1 + 2     + 3 ...     + N
        // sum = N + (N-1) + (N-2) ... + 1
        // sum + sum = (N + 1) + (N + 1) ... + (N + 1) // term (N+1) occurs N times
        // 2 x sum = N x (N + 1)
        //
    }
}

for i in 0...10 {
    let sum = Algo1.sum (to: UInt (i))
    print ("sum: \(0) to \(i) = \(sum)")
    assert (sum == Algo2.sum (to: UInt (i)))
}
3

You've done a good job already because this is a straight product problem. The Algorithms package should be able to help you, but without variadic generics, its product solution is lacking for any deeper nesting than two for loops. As is noted on that page, you'll need to write your own functions for higher arities.

product(1...3, Shape.allCases, Shading.allCases, Color.allCases).map(Card.init)

enum Shape: CaseIterable {
  case diamond, squiggle, oval
}

enum Shading: CaseIterable {
  case solid, striped, open
}

enum Color: CaseIterable {
  case red, green, purple
}

struct Card {
  let number: Int
  let shape: Shape
  let shading: Shading
  let color: Color
}

This is about as simple as it gets, not requiring any more types:

import Algorithms

public typealias Product3Collection<
  Base1: Collection, Base2: Collection, Base3: Collection
> = LazyMapCollection<
  Product2Sequence<Base1, Product2Sequence<Base2, Base3>>,
  (Base1.Element, Base2.Element, Base3.Element)
>

@inlinable
public func product<Base1, Base2, Base3>(
  _ s1: Base1, _ s2: Base2, _ s3: Base3
) -> Product3Collection<Base1, Base2, Base3> {
  product(s1, product(s2, s3)).lazy.map { ($0, $1.0, $1.1) }
}

public typealias Product4Collection<
  Base1: Collection, Base2: Collection, Base3: Collection, Base4: Collection
> = LazyMapCollection<
  Product2Sequence<Base1, Product3Collection<Base2, Base3, Base4>>,
  (Base1.Element, Base2.Element, Base3.Element, Base4.Element)
>

@inlinable
public func product<Base1, Base2, Base3, Base4>(
  _ s1: Base1, _ s2: Base2, _ s3: Base3, _ s4: Base4
) -> Product4Collection<Base1, Base2, Base3, Base4> {
  product(s1, product(s2, s3, s4)).lazy.map { ($0, $1.0, $1.1, $1.2) }
}
1 Like
4

Hi Jessy,

Thanks for posting your reply and solution.

You've pointed me onto the product algorithm. I managed to construct the card variations using product but noticed the result for each card is a nested tuple.

I can see that's what you're doing with lazy.map { ... } to create a new tuple that combines the elements.

You've also sprinkled in some other unfamiliar syntax that I'll have to research. But the essence of what you're doing is creating nested products that's eventually flattened.

I was getting caught up trying to use compactMap to flatten the product's result. That's when I spotted your use of map.

Here's is what I was able to come up with that replicates the behaviour.

struct Card {
    
    let shape:Int
    let number:Int
    let colour:Int
    let shading:Int
    
}

let levelOne = product(variations, variations)
let levelTwo = product(levelOne, variations).lazy.map { ($0.0, $0.1, $1) }
let levelThree = product(levelTwo, variations).lazy.map { ($0.0, $0.1, $0.2, $1) }

let allCards = levelThree.map { Card(shape: $0, number: $1, colour: $2, shading: $3) }

allCards.forEach { print($0) }

I didn't recognise the nested tuple dot syntax at first, but then it clicked.

Out of curiosity, how do you know if the algorithmic version or the iteration version is more performant? I suspect for such a small set it's negligible.

1 Like
5

Hi ibex10,

Thanks for your reply.

I did start to read Tim Roughgarden's book and lectures that were referenced here at teachyourselfcs.com but I also don't have a strong understanding in mathematics for cs which was suggested as a prerequisite. So it seems I've got a couple of mountains to climb before hand.

6

Algorithms product is designed for heterogeneous argument types. as you said it "is lacking for any deeper nesting than two for loops". With each nesting, the result tuple get deeper and it's kind of confusing to destructure. I'm amazed at you generic code. I'm not able write code like this.

For my own need, I wrote a product function for homogeneous argument type that can take an array and computet the product result using Algorithms' product:

public func product<C: Collection>(_ terms: Array<C>) -> Array<Array<C.Element>> {
    switch terms.count {
    case 0:
        return []
    case 1:
        return terms[0].map { [$0] }
    default:
        var result = product(terms[0], terms[1]).map { [$0, $1] }
        for term in terms.dropFirst(2) {
            result = product(result, term).map { $0.0 + [$0.1] }
        }
        return result
    }
}

with this, OP's problem can be solved:

product(Array(repeating: 0...2, count: 4))

I thought support for homogeneous product argument type is a very common need so it should be built-in to Algorithms: Algorithms package: product(_:_) limited to two product terms only, for homogeneous element type, there should be one for any number of product terms?

7

Hi Brent,

Don’t fear - You have excellent communication skills.

Pick up a good book and start reading it, and spend less time with stuff available on the internet :)

Also, contrary to what is being said, Swift is definitely not a beginner’s language if you have not had any (solid) experience with the C or C++ languages. Swift provides a layer of magic between you and what goes on under the hood, providing the perfect ground for breeding programmers unaware of what really goes on.

Finally, if you want to learn practical computer science useful in real life programming, a good place to start would be the topic of compilers.
There is an excellent book on this topic, known as the Dragon Book: Compilers, Principles, Techniques, and Tools. Alfred V. Aho, Ravi Sethi, Jeffery D. Ullman. It is an ancient book, but it is the mother of all other books on compilers.

Enjoy the journey.

ibex10

8

Algorithms product is very slow in debug built (and much slower than raw loops in debug build) but very fast in optimized built. Don't know if it's faster than iteration in optimized build (I don't think it can be faster but maybe it's not too much slower).

But with Algorithms, you don't need to hand code your loop and know it's correct.

Watch this WWDC18 - Videos - Apple Developer