在這里，我試圖形成一個(gè)包含數(shù)字對(duì)的排列，每對(duì)m都由m個(gè)元素分隔。例如：對(duì)于 [0,2]，配對(duì)排列為 [2,0, 0,2]，使得 m=2，因此數(shù)字 2 被 2 個(gè)元素分隔。對(duì)于 [0,1] = 沒有有效的排列我仍然無法弄清楚排列的模式或算法，因?yàn)槲倚枰业阶疃?[0,1,2,3,4,5,6,7,8] 的排列。然而，通過手動(dòng)執(zhí)行此列表的有效排列是 [3,7,8,2,3,1,2,1,6,7,5,8,4,0,0,6,5,4] 。在下面的代碼中，我只能通過首先獲取列表中最大的數(shù)字來重新排列列表中的數(shù)字。我想知道如何根據(jù)對(duì)的數(shù)量來分離對(duì)（例如，如果對(duì)是2，則分離數(shù)是2）我怎樣才能對(duì)數(shù)字列表進(jìn)行分隔和模式？ 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) }
1 回答
嚕嚕噠
TA貢獻(xiàn)1784條經(jīng)驗(yàn) 獲得超7個(gè)贊
您似乎試圖通過將源列表加倍，然后通過重復(fù)切片和連接數(shù)組來打亂數(shù)字來找到最佳解決方案。
我認(rèn)為這個(gè)問題適合遞歸方法。創(chuàng)建具有空槽的目標(biāo)數(shù)組2 * len(list)。（槽是否為空必須用特殊值來標(biāo)記，例如-1。）然后遞歸地嘗試將原始數(shù)組的元素放入目標(biāo)數(shù)組中。
讓我們看一下您的示例 {0, 1, 3}。創(chuàng)建目標(biāo)數(shù)組：
. . . . . .
嘗試 0 的所有可能位置。第一個(gè)是
0 0 . . . .
現(xiàn)在嘗試擬合1。有兩種可能性
0 0 . . . .
0 0 1 . 1 .
但這無法容納下一個(gè)元素， 3. 返回上一步：
0 0 . . . .
0 0 . 1 . 1
3個(gè)也不適合放在這里。我們已經(jīng)用盡了對(duì)零位置的搜索，所以讓我們采取下一個(gè)可行的零位置：
. 0 0 . . .
只有一種方法可以放置它：
. 0 0 . . .
. 0 0 1 . 1
現(xiàn)在讓我們嘗試擬合 3，賓果游戲，它擬合了：
. 0 0 . . .
. 0 0 1 . 1
3 0 0 1 3 1
現(xiàn)在您可以停止搜索或嘗試尋找其他解決方案。在這種情況下，只有另一種解決方案，即該解決方案的反射，但有 300 種方法可以放置從 1 到 8 的數(shù)字，例如。
這種方法幾乎是蠻力的，但在實(shí)踐中，沒有很多有效的方法來填充數(shù)組，因此可以及早檢測(cè)到錯(cuò)誤的路徑。也許將大數(shù)字放在第一位可以提供更好的性能。您可以使用它并測(cè)量它。
這是一個(gè)可以做到這一點(diǎn)的程序。（它可能看起來更像 C 而不是 Go。沒關(guān)系。）
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");
}
- 1 回答
- 0 關(guān)注
- 135 瀏覽
添加回答
舉報(bào)
0/150
提交
取消