在 Go 中查找配对排列

Question

在这里，我试图形成一个包含数字对的排列，每对m都由m个元素分隔。例如：

• 对于 [0,2]，配对排列为 [2,0, 0,2]，使得 m=2，因此数字 2 被 2 个元素分隔。

• 对于 [0,1] = 没有有效的排列

我仍然无法弄清楚排列的模式或算法，因为我需要找到最多 [0,1,2,3,4,5,6,7,8] 的排列。然而，通过手动执行此列表的有效排列是 [3,7,8,2,3,1,2,1,6,7,5,8,4,0,0,6,5,4] 。

在下面的代码中，我只能通过首先获取列表中最大的数字来重新排列列表中的数字。我想知道如何根据对的数量来分离对（例如，如果对是2，则分离数是2）

我怎样才能对数字列表进行分隔和模式？

   package main

    import "fmt"

    func MagicPairs(list []int) {

        //length := len(list) * 2

        magicPair := []int{}

        magicPair = append(list, list...)

        for i := 0; i <len(magicPair); i++{

            if len(magicPair) == 0 {

                //do nothing

            }else{  

                m := max(list)

                for p, x := range magicPair{

                    if magicPair[len(magicPair)-1] == m {   

                        magicPair = append([]int{m}, (magicPair)[:len(magicPair)-1]...)

                        fmt.Println(magicPair)

                        return

                    }

                    if x == m{

                        magicPair = append([]int{m}, append((magicPair)[:p], (magicPair)[p+1:]...)...)

                    }

                    previousPair := magicPair[x]

                    if x == previousPair{

                    }

                }

            }

        }

        fmt.Println("1", magicPair)

    }

    func max(list[] int) int{

        max := list[0]

        for _, value := range list{

            if value > max {

                max = value 

            }

        }

        return max

    }

    func main(){

        list := [] int {0,1,2,3,4,5,6,7,8}

        MagicPairs(list)

    }

Answer 1

您似乎试图通过将源列表加倍，然后通过重复切片和连接数组来打乱数字来找到最佳解决方案。我认为这个问题适合递归方法。创建具有空槽的目标数组2 * len(list)。（槽是否为空必须用特殊值来标记，例如-1。）然后递归地尝试将原始数组的元素放入目标数组中。让我们看一下您的示例 {0, 1, 3}。创建目标数组：. . . . . .尝试 0 的所有可能位置。第一个是0 0 . . . .现在尝试拟合1。有两种可能性0 0 . . . .0 0 1 . 1 .但这无法容纳下一个元素， 3. 返回上一步：0 0 . . . .0 0 . 1 . 13个也不适合放在这里。我们已经用尽了对零位置的搜索，所以让我们采取下一个可行的零位置：. 0 0 . . .只有一种方法可以放置它：. 0 0 . . .. 0 0 1 . 1现在让我们尝试拟合 3，宾果游戏，它拟合了：. 0 0 . . .. 0 0 1 . 13 0 0 1 3 1现在您可以停止搜索或尝试寻找其他解决方案。在这种情况下，只有另一种解决方案，即该解决方案的反射，但有 300 种方法可以放置从 1 到 8 的数字，例如。这种方法几乎是蛮力的，但在实践中，没有很多有效的方法来填充数组，因此可以及早检测到错误的路径。也许将大数字放在第一位可以提供更好的性能。您可以使用它并测量它。这是一个可以做到这一点的程序。（它可能看起来更像 C 而不是 Go。没关系。）package mainimport "fmt"func fit_r(res[] int, a[] int, i int) int {&nbsp; &nbsp; n := len(a);&nbsp; &nbsp; if i == n {&nbsp; &nbsp; &nbsp; &nbsp; fmt.Printf("%v\n", res);&nbsp; &nbsp; &nbsp; &nbsp; return 1;&nbsp; &nbsp; } else {&nbsp; &nbsp; &nbsp; &nbsp; count := 0;&nbsp; &nbsp; &nbsp; &nbsp; m := a[i];&nbsp; &nbsp; &nbsp; &nbsp; for j := 0; j < 2*n - 1 - m; j++ {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if res[j] == -1 && res[j + 1 + m] == -1 {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; // place values&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; res[j] = m;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; res[j + 1 + m] = m;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; // test further values&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; count += fit_r(res, a, i + 1);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; // clean up and remove values again&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; res[j] = -1;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; res[j + 1 + m] = -1;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp;&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; return count;&nbsp; &nbsp; }}func fit(a[] int) int {&nbsp; &nbsp; res := make([] int, 2 * len(a));&nbsp; &nbsp; for i := range res {&nbsp; &nbsp; &nbsp; &nbsp; res[i] = -1;&nbsp; &nbsp; }&nbsp; &nbsp; return fit_r(res, a, 0);}func main() {&nbsp; &nbsp; list := [] int {0, 1, 2, 3};&nbsp; &nbsp; n := fit(list);&nbsp; &nbsp; fmt.Println(n, "solutions");}