哈希遊戲中島嶼的每一個可能的連擊

爲了解決這個問題，我需要找到每個島嶼周圍所有可能的鏈接+島嶼組合。

約束條件是1或2個鏈接，一個組合就是爲目標島創建的足夠鏈接。

例如，我有一個島['A' => 3]，這意味着它需要3個鏈接來解決，它有3個鄰居['B', 'C', 'D']。

我想找到這將產生這樣的陣列的算法：

[ 
    ['B' => 1, 'C' => 1, 'D' => 1], 
    ['B' => 1, 'C' => 2], 
    ['B' => 1, 'D' => 2], 
    ['B' => 2, 'C' => 1], 
    ['B' => 2, 'D' => 1], 
    ['C' => 1, 'D' => 2], 
    ['C' => 2, 'D' => 1] 
];

感謝。

來源

2017-06-03 Steve Chamaillard

如果你想要我們解決你的功課，也許你可以至少描述一下，這樣我們就不必研究你想要解決的遊戲規則了？ –

你爲什麼認爲你需要創建這些組合？我認爲頂點（每個頂點可以有1到4個鄰居）以及具有權重元素{0,1,2}的鄰居之間的鏈接是最容易的。鏈接的總和必須匹配頂點。許多鏈接可以通過簡單的規則添加。其餘的你可以使用回溯。您必須確保在添加鏈接時移除鏈接。 – maraca

我已經解決了這個問題。我談到了遊戲的背景。這不是一項家庭作業。我只是尋找另一種實現這種邏輯的方式。我的問題只集中在尋找與鄰居可能的每種組合。容易解決，路徑穿越，回溯追蹤不是問題的主題。所有需要回答的元素都在問題中，鏈接僅用於好奇並回答'你爲什麼需要這樣做？'。 –

如果你想找到的鏈接的所有組合（0，1，或2）按鄰居，與鏈接固定總數，那麼你可以使用下面的遞歸函數：

function getPossibleLinks($value, $neighbors) { 
    if ($value == 0) return [[]]; 
    $max = min(2, $value); 
    $min = 2 - min(count($neighbors) * 2 - $value, 2); 
    if ($min > 2) { 
     throw new Exception('Not possible to assign that many links'); 
    } 
    $results = []; 
    for ($count = $min; $count <= $max; $count++) { 
     $nextResults = getPossibleLinks($value - $count, array_slice($neighbors, 0, -1)); 
     foreach($nextResults as $result) { 
      if ($count) $result[end($neighbors)] = $count; 
      $results[] = $result; 
     } 
    } 
    return $results; 
}

你會需要將鏈接的數量作爲第一個參數（$value），並將相鄰數組作爲字符串數組傳遞給它。

下面是一個例子電話：

$results = getPossibleLinks(3, ["B", "C", "D"]);

這個電話後，$results都會有這樣的內容：

[ 
    ['B' => 2, 'C' => 1], 
    ['B' => 1, 'C' => 2], 
    ['B' => 2, 'D' => 1], 
    ['B' => 1, 'C' => 1, 'D' => 1], 
    ['C' => 2, 'D' => 1], 
    ['B' => 1, 'D' => 2], 
    ['C' => 1, 'D' => 2] 
]

看到它在eval.in運行。

來源

2017-06-04 18:36:08 trincot

哈希遊戲中島嶼的每一個可能的連擊

回答

相關問題