2013-10-14 58 views
1

我有一個項目的數組列表,每個項目都有一個將任何其他項目作爲參數的方法。什麼是確保我在每一對可能的項目上調用方法而不重複它們的最有效方法? (所有項目可以被認爲是唯一的)。從ArrayList的所有組合調用方法的最有效方法?

我的代碼:

public boolean hasConflict (ArrayList<Item> items) { 
    // For every possible pair of items... 
     one = items.get(i); 
     two = items.get(j); 

     if (one.conflictsWith (two)) { 
      return true; 
     } 

    // If we reach the end of the list without finding a conflict 
    return false; 
} 

編輯:

one.conflictsWith (two)將返回相同的值two.conflictsWith (one),道歉忘記了。

conflictsWith方法是不比較,看看這兩個值是否重複,所以不幸的是我不能用一個哈希表來排序它。

+3

不one.conflictsWith(二)返回相同的two.conflictsWith(一個)? – dckuehn

回答

3

簡單,如果你不需要調用a.conflictsWith(b)以及b.conflictsWith(a)您可以通過節省時間:

for(int i = 0; i < list.size(); ++i) { 
    final MyClass curr = list.get(i); 
    for(int j = i + 1; j < list.size(); ++j) { 
     curr.conflictsWith(list.get(j)); 
    } 
} 

即環比List,然後,在第二循環中,遍歷List的其餘部分

否則,你需要循環一切

for(int i = 0; i < list.size(); ++i) { 
    final MyClass curr = list.get(i); 
    for(int j = 0; j < list.size(); ++j) { 
     if(i != j) { 
      curr.conflictsWith(list.get(j)); 
     }   
    } 
} 
+0

不認爲這將涵蓋所有組合。如果我= 10個組合像(10,0)永遠不會執行 –

+0

@DevBlanked已經添加了一個更透徹的解釋。 –

+0

在您的對稱情況下,您還需要a.conflictWith(a)始終爲false。 –

1

如果conflictsWith()是對稱的,即one.conflictsWith(two) == two.conflictsWith(one)每對的參數,然後使用:

for (int i = 0; i < items.size(); i++) 
{ 
    final Item one = items.get(i); 
    for (int j = i + 1; j < items.size(); j++} 
    { 
     one.conflictsWith(items.get(j)); 
    } 
} 

如果不是對稱的,你必須再檢查兩次:

for (int i = 0; i < items.size(); i++) 
{ 
    final Item one = items.get(i); 
    for (int j = 0; j < items.size(); j++} // only this line changed 
    { 
     one.conflictsWith(items.get(j)); 
    } 
} 

最後一個也會檢查one.conflictsWith(one)。如果這是個問題,請使用if (i != j)

1

因爲我們不知道什麼是「衝突」的意思,即如果例如a.conflictsWith(b)a. conflictsWith(c)說s.th約b.conflictsWith(c),你需要接觸每個組合,IE瀏覽器

for(int i=0; i< items.size(); i++) { 
    Item item = items.get(i); 
    for(int j=0; j< items.size(); j++) 
     if(item.conflictsWith(items.get(j)) return true; 
    } 
    } 
    return false; 

如果關係conflictWith是對稱的,如果a.conflictsWith(一)始終是假的,你可以使用

for(int i=0; i< items.size(); i++) { 
    Item item = items.get(i); 
    for(int j=i+1; j< items.size(); j++) 
     if(item.conflictsWith(items.get(j)) return true; 
    } 
    } 
    return false;