Functional clustering of array values ​​in Swift

Question

Given an array, for example:

[0, 0.5, 0.51, 1.0, 1.5, 1.99, 2.0, 2.1, 2.5, 3.0] 

I want to group values ​​into subarrays based on their successive differences (e.g. where abs(x-y) < nand n = 0.2), for example:

[[0], [0.5, 0.51], [1.0], [1.5], [1.99, 2.0, 2.1], [2.5], [3.0]]. 

I would like to do this declaratively - just to better understand how more complex sequence operations can work in a functional context (it seems that most of the "functional Swift" demos / tutorials are pretty simple).

Thanks in advance.

---

Update:

Here is a single line that seems to be close:

let times = [0, 0.5, 0.99, 1, 1.01, 1.5, 2, 2.5, 2.51, 3, 3.49, 3.5]

let result = times.map { t1 in
    return times.filter { fabs($0 - t1) < 0.2 }
}

// [[0.0], [0.5], [0.99, 1.0, 1.01], [0.99, 1.0, 1.01], [0.99, 1.0, 1.01], [1.5], [2.0], [2.5, 2.51], [2.5, 2.51], [3.0], [3.49, 3.5], [3.49, 3.5]]

You just need to get rid of duplicates.

Answer 1

. Btw , , , , . , " " , . .

let a : [Double] = [0, 0.5, 0.51, 1.0, 1.5, 1.99, 2.0, 2.1, 2.5, 3.0];
let diff : Double = 0.2;
let eps = 0.0000001

let b = a.sort().reduce(([],[])) { (ps : ([Double],[[Double]]), c : Double) -> ([Double],[[Double]]) in
  if ps.0.count == 0 || abs(ps.0.first! - c) - diff <= eps { return (ps.0 + [c], ps.1) } else { return ([c], ps.1 + [ps.0]) }
}
let result = b.1 + [b.0];
print(result)

[[0.0], [0.5, 0.51], [1.0], [1.5], [1.99, 2.0, 2.1], [2.5], [3.0]]

Answer 2

Swift, , . :

extension Array {
    func split(condition : (Element, Element) -> Bool) -> [[Element]] {
        var returnArray = [[Element]]()

        var currentSubArray = [Element]()

        for (index, element) in self.enumerate() {
            currentSubArray.append(element)

            if index == self.count - 1 || condition(element, self[index+1]) {
                returnArray.append(currentSubArray)
                currentSubArray = []
            }
        }

        return returnArray
    }
}

:

let source = [0, 0.5, 0.51, 1.0, 1.5, 1.99, 2.0, 2.1, 2.5, 3.0]
let n = 0.2
let target = source.split { abs($0 - $1) > n }

:

[[0.0], [0.5, 0.51], [1.0], [1.5], [1.99, 2.0, 2.1], [2.5], [3.0]]

Answer 3

:

extension Array {
    func split(condition : (Element, Element) -> Bool) -> [[Element]] {
        return self.reduce([], combine:
            { (list : [[Element]], value : Element) in
                if list.isEmpty {
                    return [[value]]
                }
                else if !condition(list.last!.last!, value) {
                    return list[0..<list.count - 1] + [list.last!+[value]]
                }
                else {
                    return list + [[value]]
                }
            }
        )
    }
}

let source = [0, 0.5, 0.51, 1.0, 1.5, 1.99, 2.0, 2.1, 2.5, 3.0]
let n = 0.2
let target = source.split { abs($0 - $1) > n }

:

[[0], [0.5, 0.51], [1], [1.5], [1.99, 2, 2.1], [2.5], [3]]

, :

extension Array {
    func split(condition : (Element, Element) -> Bool) -> [[Element]] {
        return self.reduce([], combine:
            { ( var list : [[Element]], value : Element) in
                if list.isEmpty || condition(list.last!.last!, value) {
                    list += [[value]]
                }
                else {
                    list[list.count - 1] += [value]
                }
                return list
            }
        )
    }
}

Answer 4

Swift .

, if/else : ( , )

let values:[Double] = [0, 0.5, 0.51, 1.0, 1.5, 1.99, 2.0, 2.1, 2.5, 3.0]

let inGroup     = { (x:Double,y:Double) return abs(x-y) < 0.2 }

let intervals   = zip(values,values.enumerated().dropFirst())            
let starts      = intervals.filter{ !inGroup($0,$1.1) }.map{$0.1.0}
let ranges      = zip([0]+starts, starts+[values.count])
let result      = ranges.map{values[$0..<$1]}

//  result :  [ [0.0], [0.5, 0.51], [1.0], [1.5], [1.99, 2.0, 2.1], [2.5], [3.0]  ]             

//  how it works ...
//
//  intervals:   Contains pairs of consecutive values along with the index of second one
//               [value[i],(index,value[i+1])] 
//
//  starts:      Contains the index of second values that don't meet the grouping condition 
//               (i.e. start of next group) 
//               [index] 
//        
//  ranges:      Contains begining and end indexes for group ranges formed using start..<end
//               [(Int,Int)]
//
//  result:      Groups of consecutive values meeting the inGroup condition
//                

Answer 5

I would do it like Aaron Brager does. This, IMO, is Swift's best approach. Swift doesn't really play well with functional programming. But to explore as you can, here is one way I could attack him.

I fully expect the performance on this to be terrible. Probably O (n ^ 2). Recursively expanding the array, as I do in groupWhile, makes it copy the entire array at every step.

// Really Swift? We have to say that a subsequence has the same elements as its sequence?
extension CollectionType where SubSequence.Generator.Element == Generator.Element {

    // Return the prefix for which pred is true, and the rest of the elements.
    func span(pred: Generator.Element -> Bool) -> ([Generator.Element], [Generator.Element]) {
        let split = indexOf{ !pred($0) } ?? endIndex
        return (Array(self[startIndex..<split]), Array(self[split..<endIndex]))
    }

    // Start a new group each time pred is false.
    func groupWhile(pred: Generator.Element -> Bool) -> [[Generator.Element]] {
        guard self.count > 0 else { return [] }
        let (this, that) = span(pred)
        let next = that.first.map{[$0]} ?? []
        let rest = Array(that.dropFirst())
        return [this + next] + rest.groupWhile(pred)
    }
}

extension CollectionType where
    Generator.Element : FloatingPointType,
    Generator.Element : AbsoluteValuable,
    SubSequence.Generator.Element == Generator.Element {

    //
    // Here the meat of it
    //
    func groupBySeqDistanceGreaterThan(n: Generator.Element) -> [[Generator.Element]] {

        // I don't love this, but it is a simple way to deal with the last element.
        let xs = self + [Generator.Element.infinity]

        // Zip us with our own tail. This creates a bunch of pairs we can evaluate.
        let pairs = Array(zip(xs, xs.dropFirst()))

        // Insert breaks where the difference is too high in the pair
        let groups = pairs.groupWhile { abs($0.1 - $0.0) < n }

        // Collapse the pairs down to values
        return groups.map { $0.map { $0.0 } }
    }
}