Go中的查找对安排

Question

这里，我试图形成一种包含数对的排列，每对m's用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 . 1

3个也不适合在这里。我们已经穷尽了对零位置的搜索，因此让我们考虑下一个可行的零位置：

. 0 0 . . .

只有一种放置方式：

. 0 0 . . .
. 0 0 1 . 1

现在让我们尝试将3和bingo！放在一起：

. 0 0 . . .
. 0 0 1 . 1
3 0 0 1 3 1

现在您可以停止搜索或尝试找到其他解决方案。在这种情况下，只有另一种解决方案，即对此解决方案的反思，但是有300种方法可以将数字从1放置到8，这是示例。

这种方法几乎是蛮力的，但是在实践中，没有很多有效的方法来填充数组，因此可以及早发现错误的路径。也许将大量数字放在首位可以带来更好的性能。您可以使用它并对其进行测量。

这里是一个执行此操作的程序。 （可能看起来比C更像C。没关系。）

package main

import "fmt"

func fit_r(res[] int, a[] int, i int) int {
    n := len(a);

    if i == n {
        fmt.Printf("%v\n", res);
        return 1;
    } else {
        count := 0;
        m := a[i];

        for j := 0; j < 2*n - 1 - m; j++ {
            if res[j] == -1 && res[j + 1 + m] == -1 {
                // place values
                res[j] = m;
                res[j + 1 + m] = m;

                // test further values
                count += fit_r(res, a, i + 1);

                // clean up and remove values again
                res[j] = -1;
                res[j + 1 + m] = -1;
            }
        }        

        return count;
    }
}

func fit(a[] int) int {
    res := make([] int, 2 * len(a));

    for i := range res {
        res[i] = -1;
    }

    return fit_r(res, a, 0);
}

func main() {
    list := [] int {0, 1, 2, 3};
    n := fit(list);

    fmt.Println(n, "solutions");
}