我一直想知道這個問題是否有更好的解決方案：假設有n 個容器（它們的長度可能不同）。在他們每個人中，我們都有一些數字。通過從每個容器中取出一個元素而創建的 n 長度陣列的數量是多少？新形成的陣列中的那些數字必須是唯一的（例如，不能創建 (2,3,3) 但可以創建 (2,4,3)）。這是一個例子：
n=3
c1=(1,6,7)
c2=(1,6,7)
c3=(6,7)
正確答案是 4，因為我們可以創建這四個陣列：(1,6,7), (1,7,6), (6,1,7), (6,7,1)。
編輯：n 個容器中沒有一個包含重復項，并且新陣列中的所有元素的順序必須與它們所屬的容器的順序相同。
所以我的問題是：除了生成每一種可能性并檢查它是否沒有重復之外，還有什么更好的方法來計算這些陣列的數量？
uj5u.com熱心網友回復：
您不需要生成每種可能性，然后檢查它是否有重復 - 您可以在添加可能重復的元素之前執行此操作，從而進一步節省大量浪費的作業。但是，是的，鑒于要求
新陣列中的所有元素的順序必須與它們所屬的容器的順序相同
你不能簡單地計算排列或 m-over-n 的組合，這會更快（因為有一個封閉的公式）。
因此，最佳演算法可能是使用帶有集合的回溯方法來避免在構建部分答案時出現重復，并計算找到的有效答案的數量。
這個問題看起來有點像計算一維數獨的可能答案：從每個區域中選擇一個元素，確保沒有重復。在許多情況下，可能有 0 個答案 - 想象一下n=4, c=[[1,2],[2,3],[3,1],[2,3]]。例如，如果容器k子集的元素少于唯一元素，k則不可能有答案。
轉載請註明出處，本文鏈接：https://www.uj5u.com/gongcheng/327566.html
下一篇：理解連續子陣列求和問題