2
\$\begingroup\$

For a project I'm working on I have a set of number sets, and I need all unique permutations of them. I want to return only one copy of each unique number set, and I'm struggling to figure out how without some really funky design patterns. Maybe I had a moment of genius, but I doubt it, it really seems like there's a better way. To clarify the problem, my very initial effort yielded this unacceptable output (i.e. redundant, deep-equal slices):

[22 4]
[4 22]
[21 5]
[5 21]
[20 6]
[6 20]
[19 7]
[7 19]
[18 8]
[8 18]
[18 4 4]
[4 18 4]
[4 4 18]
[4 4 18]
[4 18 4]
[18 4 4]
[17 9]
[9 17]
[17 4 5]
[4 17 5]
[5 4 17]
[4 5 17]
[5 17 4]
[17 5 4]
[16 10]
[10 16]
[16 4 6]
[4 16 6]
[6 4 16]
[4 6 16]
[6 16 4]
[16 6 4]
[16 5 5]
[5 16 5]
[5 5 16]
[5 5 16]
[5 16 5]
[16 5 5]
[15 11]
[11 15]
[15 4 7]
[4 15 7]
[7 4 15]
[4 7 15]
[7 15 4]
[15 7 4]
[15 5 6]
[5 15 6]
[6 5 15]
[5 6 15]
[6 15 5]
[15 6 5]
[14 12]
[12 14]
[14 4 8]
[4 14 8]
[8 4 14]
[4 8 14]
[8 14 4]
[14 8 4]
[14 5 7]
[5 14 7]
[7 5 14]
[5 7 14]
[7 14 5]
[14 7 5]
[14 6 6]
[6 14 6]
[6 6 14]
[6 6 14]
[6 14 6]
[14 6 6]
[13 13]
[13 13]
[13 4 9]
[4 13 9]
[9 4 13]
[4 9 13]
[9 13 4]
[13 9 4]
[13 5 8]
[5 13 8]
[8 5 13]
[5 8 13]
[8 13 5]
[13 8 5]
[13 6 7]
[6 13 7]
[7 6 13]
[6 7 13]
[7 13 6]
[13 7 6]
[12 4 10]
[4 12 10]
[10 4 12]
[4 10 12]
[10 12 4]
[12 10 4]
[12 5 9]
[5 12 9]
[9 5 12]
[5 9 12]
[9 12 5]
[12 9 5]
[12 6 8]
[6 12 8]
[8 6 12]
[6 8 12]
[8 12 6]
[12 8 6]
[12 7 7]
[7 12 7]
[7 7 12]
[7 7 12]
[7 12 7]
[12 7 7]
[11 4 11]
[4 11 11]
[11 4 11]
[4 11 11]
[11 11 4]
[11 11 4]
[11 5 10]
[5 11 10]
[10 5 11]
[5 10 11]
[10 11 5]
[11 10 5]
[11 6 9]
[6 11 9]
[9 6 11]
[6 9 11]
[9 11 6]
[11 9 6]
[11 7 8]
[7 11 8]
[8 7 11]
[7 8 11]
[8 11 7]
[11 8 7]

My goal, which I accomplished was to make it look like:

[22 4]
[4 22]
[21 5]
[5 21]
[20 6]
[6 20]
[19 7]
[7 19]
[18 8]
[8 18]
[4 4 18]
[4 18 4]
[18 4 4]
[17 9]
[9 17]
[17 4 5]
[4 17 5]
[5 4 17]
[4 5 17]
[5 17 4]
[17 5 4]
[16 10]
[10 16]
[16 4 6]
[4 16 6]
[6 4 16]
[4 6 16]
[6 16 4]
[16 6 4]
[5 5 16]
[5 16 5]
[16 5 5]
[15 11]
[11 15]
[15 4 7]
[4 15 7]
[7 4 15]
[4 7 15]
[7 15 4]
[15 7 4]
[15 5 6]
[5 15 6]
[6 5 15]
[5 6 15]
[6 15 5]
[15 6 5]
[14 12]
[12 14]
[14 4 8]
[4 14 8]
[8 4 14]
[4 8 14]
[8 14 4]
[14 8 4]
[14 5 7]
[5 14 7]
[7 5 14]
[5 7 14]
[7 14 5]
[14 7 5]
[6 6 14]
[6 14 6]
[14 6 6]
[13 13]
[13 4 9]
[4 13 9]
[9 4 13]
[4 9 13]
[9 13 4]
[13 9 4]
[13 5 8]
[5 13 8]
[8 5 13]
[5 8 13]
[8 13 5]
[13 8 5]
[13 6 7]
[6 13 7]
[7 6 13]
[6 7 13]
[7 13 6]
[13 7 6]
[12 4 10]
[4 12 10]
[10 4 12]
[4 10 12]
[10 12 4]
[12 10 4]
[12 5 9]
[5 12 9]
[9 5 12]
[5 9 12]
[9 12 5]
[12 9 5]
[12 6 8]
[6 12 8]
[8 6 12]
[6 8 12]
[8 12 6]
[12 8 6]
[7 7 12]
[7 12 7]
[12 7 7]
[11 4 11]
[4 11 11]
[11 11 4]
[11 5 10]
[5 11 10]
[10 5 11]
[5 10 11]
[10 11 5]
[11 10 5]
[11 6 9]
[6 11 9]
[9 6 11]
[6 9 11]
[9 11 6]
[11 9 6]
[11 7 8]
[7 11 8]
[8 7 11]
[7 8 11]
[8 11 7]
[11 8 7]

But I'm pretty confident that there must be a better way than what I did. There is also a possibility I'm solving this in the wrong place. The permutations function is a shameless copy+paste+amend, and maybe I could be doing something there to avoid the messy output. At the very least, I have to be using way too much control flow here:

func main() {
    (...)
    sets := [][]int{
        []int{22, 4},
        []int{21, 5},
        []int{20, 6},
        []int{19, 7},
        []int{18, 8},
        []int{18, 4, 4},
        []int{17, 9},
        []int{17, 4, 5},
        []int{16, 10},
        []int{16, 4, 6},
        []int{16, 5, 5},
        []int{15, 11},
        []int{15, 4, 7},
        []int{15, 5, 6},
        []int{14, 12},
        []int{14, 4, 8},
        []int{14, 5, 7},
        []int{14, 6, 6},
        []int{13, 13},
        []int{13, 4, 9},
        []int{13, 5, 8},
        []int{13, 6, 7},
        []int{12, 4, 10},
        []int{12, 5, 9},
        []int{12, 6, 8},
        []int{12, 7, 7},
        []int{11, 4, 11},
        []int{11, 5, 10},
        []int{11, 6, 9},
        []int{11, 7, 8},
    }

    for _, set := range sets {
        nextIntSlice := permutations(set)

        clean := false
        for clean == false {
            nextIntSlice, clean = myBadWannaBeRecursiveFilter(nextIntSlice)
        }

        for _, iSlice := range nextIntSlice {
            cleanSlice = append(cleanSlice, iSlice)
        }
    }
    (...)
}

func myBadWannaBeRecursiveFilter(dirtySliceOfSlices [][]int) ([][]int, bool) {
    stillDirty := false
    var stillDirtySlice [][]int

    for i, sliceA := range dirtySliceOfSlices {
        counter := 0
        for _, sliceB := range dirtySliceOfSlices {
            dup := testSliceIntEq(sliceA, sliceB)
            if dup {
                counter++
            }

            if counter > 1 {
                stillDirty = true
                p1 := dirtySliceOfSlices[:i]
                p2 := dirtySliceOfSlices[i+1:]

                if len(p1) > 0 {
                    for _, s := range p1 {
                        stillDirtySlice = append(stillDirtySlice, s)
                    }
                }

                if len(p2) > 0 {
                    for _, s := range p2 {
                        stillDirtySlice = append(stillDirtySlice, s)
                    }
                }

                //  ORIGINALLY TRIED:
                // dirtySliceOfSlices = append(dirtySliceOfSlices[:i], dirtySliceOfSlices[i+1:])
                // ^^^^^^^^^^^ THIS GENERATES THE COMPILE TIME ERR:
                // cannot use dirtySliceOfSlices[i + 1:] (type [][]int) as type []int in append
                // Which makes sense, but I don't know how to get around when using slices of slices other than control flow within control flow.

                break
            }
        }

        if stillDirty {
            break
        }
    }

    if stillDirty {
        return stillDirtySlice, false
    }

    return dirtySliceOfSlices, true
}

func testSliceIntEq(a, b []int) bool {

    // If one is nil, the other must also be nil.
    if (a == nil) != (b == nil) {
        return false
    }

    if len(a) != len(b) {
        return false
    }

    for i := range a {
        if a[i] != b[i] {
            return false
        }
    }

    return true
}       

func permutations(arr []int) [][]int {
    var helper func([]int, int)
    res := [][]int{}

    helper = func(arr []int, n int) {
        if n == 1 {
            tmp := make([]int, len(arr))
            copy(tmp, arr)
            res = append(res, tmp)
        } else {
            for i := 0; i < n; i++ {
                helper(arr, n-1)
                if n%2 == 1 {
                    tmp := arr[i]
                    arr[i] = arr[n-1]
                    arr[n-1] = tmp
                } else {
                    tmp := arr[0]
                    arr[0] = arr[n-1]
                    arr[n-1] = tmp
                }
            }
        }
    }
    helper(arr, len(arr))
    return res
}

Special thanks to StackOverflow for the slice comparison func, and some random internet article for permutations. Bottom line, my program works, but I don't feel like I learned anything good from it. Maybe you guys can help.

\$\endgroup\$

Your Answer

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

Browse other questions tagged or ask your own question.