Java的遞歸組合函數迭代相當於

Question

我有遞歸合併功能：

static void combinations2(String[] arr, int len, int startPosition, String[] result) { 

    if (len == 0) { 
     for (String n : result) { 
      System.out.print(n + " \n"); 

     } 

     return; 
    } 

    for (int i = startPosition; i <= arr.length - len; i++) { 
     result[result.length - len] = arr[i]; 
     combinations2(arr, len - 1, i + 1, result); 
    } 
} 

輸入：

arr = {"Item 1", "Item 2", "Item 3", "Item 4", "Item 5"} - input array e.g. 
len = 3 - length of each combination 
startPosition = 0 
result - result of each combination 

輸出：

Item 1 
Item 2 
Item 3 

Item 1 
Item 2 
Item 4 

Item 1 
Item 2 
Item 5 

Item 1 
Item 3 
Item 4 

Item 1 
Item 3 
Item 5 

Item 1 
Item 4 
Item 5 

Item 2 
Item 3 
Item 4 

Item 2 
Item 3 
Item 5 

Item 2 
Item 4 
Item 5 

Item 3 
Item 4 
Item 5 

我應該怎麼做將其更改爲迭代替代？我閱讀了關於堆棧的內容，並且我寫了幾行代碼......但是返回函數呢？如何處理它？

我做了財產以後這樣的：

static void combinations2(String[] arr, int len, int startPosition, String[] result) { 
     Stack<Integer> stos = new Stack<>(); 
     stos.push(startPosition); 
     stos.push(len); 

     int i = 0; 
     while (!stos.isEmpty()) { 
      len = stos.pop(); 
      startPosition = stos.pop(); 

      if (len == 0) { 
       for (String n : result) { 
        System.out.print(n + " \n"); 
       }    

       System.out.println(" "); 
       stos.push(startPosition); 
       stos.push(len+1); 
      } else { 

       for (i = startPosition; i <= arr.length - len; i++) { 
        result[result.length - len] = arr[i]; 

        //combinations2(arr, len - 1, i + 1, result); 
        stos.push(i + 1); 
        stos.push(len - 1); 
        break; 

       } 
      } 
     } 
    } 

，我已經得到了輸出：

Item 1 
Item 2 
Item 3 

Item 1 
Item 2 
Item 4 

Item 1 
Item 2 
Item 5 

有人能告訴我的方式，生成接下來的步驟？

Answer 1

以下類是返回組合的Iterable。請參閱main使用方法。運行主要的方法來測試。

組合是懶洋洋地創建的，因此從10​​000000池中讀取10個元素的前100個組合不會很慢。

該課程還對任何不可能情景的探索進行了短路，即對於5個元素中的3個元素的組合，將第4個元素放置在第1個位置是毫無意義的，因爲這將導致第5個元素處於第2個位置，並且沒有元素爲最後的位置。

遞歸算法的一般迭代版本使用堆棧來模擬傳遞給相同函數的變量。

public class Combinations<T> implements Iterable<List<T>> { 

    private final List<T> items; 
    private final int size; 

    public static <T> Combinations<T> of(List<T> items, int size) { 
     return new Combinations<T>(items, size); 
    } 

    private Combinations(List<T> items, int size) { 
     if (items.size() < size) throw new IllegalArgumentException(); 
     this.items = items; 
     this.size = size; 
    } 

    public Iterator<List<T>> iterator() { 
     return new Iterator<List<T>>() {   
      private final int[] positions = new int[size];    
      private boolean more = true; 
      { 
       for(int i = 0;i < positions.length;i++) { 
        positions[i] = i; 
       } 
      } 

      public boolean hasNext() { 
       return more; 
      } 

      public List<T> next() { 
       if (!more) throw new NoSuchElementException(); 
       List<T> ret = new ArrayList<T>(); 
       for (int i = 0;i < positions.length;i++) { 
        ret.add(items.get(positions[i])); 
       } 
       int advanceIdx = positions.length - 1; 
       while(advanceIdx > -1) { 
        if (positions[advanceIdx] == items.size() - size + advanceIdx) { 
         advanceIdx--; 
        } else { 
         positions[advanceIdx]++; 
         for (int i = 1;i + advanceIdx < positions.length;i++) { 
          positions[advanceIdx+i] = positions[advanceIdx] + i; 
         } 
         return ret; 
        } 
       } 
       more = false; 
       return ret; 
      } 

      public void remove() { 
       throw new UnsupportedOperationException(); 
      } 

     }; 
    } 

    public static void main(String[] args) { 
     for(List<String> s : Combinations.of(Arrays.asList("A", "B", "C", "D", "E"), 3)) { 
      System.out.println(s); 
     } 
    } 
}