多個陣列的笛卡爾乘積

我認爲這基本上是一個簡單的問題，但我卡住了。我的大腦被這個問題所阻擋，所以我希望你能幫助我。我有2爲整數N個陣列，像多個陣列的笛卡爾乘積

{1,2,3,4,5} 
{1,2,3,4,5,6} 
{1,3,5} 
.....

現在我想有含INT [N]的陣列，每posibillity列表等

{1,1,1} 
{1,1,3} 
{1,1,5} 
{1,2,1} 
.... 
{1,3,1} 
.... 
{2,1,1} 
{2,1,3} 
.... 
{5,6,5}

所以有6 * 5 *其中有3（90）個元素。

有沒有一個簡單的算法來做到這一點？我認爲語言並不重要，但我更喜歡Java。

來源

2011-10-30 Rafael T

您要搜索的「笛卡爾積算法」。使用這個關鍵字試試Google。 –

這裏http://stackoverflow.com/questions/1140164/scala-can-yield-be-used-multiple-times-with-a-for-loop/5177163#5177163是一個簡短的遞歸解決方案在斯卡拉。 –

@userunknown對不起，我不能讀了... Scala是怪異的，我從來沒有與它的工作...其它遞歸解決方案表示讚賞 –

Thx的幫助！我在java中爲下一個有相同問題的人添加了一個有效的答案。我這樣做，也是通用的，因此美國可以對任何對象的任何笛卡兒積，而不僅僅是整數：

public class Product { 

    @SuppressWarnings("unchecked") 
    public static <T> List<T[]> getCartesianProduct(T[]... objects){ 
     List<T[]> ret = null; 
     if (objects != null){    
      //saves length from first dimension. its the size of T[] of the returned list 
      int len = objects.length; 
      //saves all lengthes from second dimension 
      int[] lenghtes = new int[len]; 
      // arrayIndex 
      int array = 0; 
      // saves the sum of returned T[]'s 
      int lenSum = 1; 
      for (T[] t: objects){ 
       lenSum *= t.length; 
       lenghtes[array++] = t.length; 
      } 
      //initalize the List with the correct lenght to avoid internal array-copies 
      ret = new ArrayList<T[]>(lenSum); 
      //reusable class for instatiation of T[] 
      Class<T> clazz = (Class<T>) objects[0][0].getClass(); 
      T[] tArray; 
      //values stores arrayIndexes to get correct values from objects 
      int[] values = new int[len]; 

      for (int i = 0; i < lenSum; i++){ 
       tArray = (T[])Array.newInstance(clazz, len); 
       for (int j = 0; j < len; j++){ 
        tArray[j] = objects[j][values[j]]; 
       } 
       ret.add(tArray); 
       //value counting: 
       //increment first value 
       values[0]++; 
       for (int v = 0; v < len; v++){ 
        //check if values[v] doesn't exceed array length 
        if (values[v] == lenghtes[v]){ 
         //set it to null and increment the next one, if not the last 
         values[v] = 0; 
         if (v+1 < len){ 
          values[v+1]++; 
         } 
        } 
       } 

      } 
     } 
     return ret; 
    } 
}

來源

2011-10-30 17:00:59

-1

正如我明白你想要什麼，你需要得到所有的排列組合。使用遞歸算法，詳細here。

來源

2011-10-30 14:49:07 mishadoff

我認爲OP要2到N的笛卡爾乘積集合，而不是給定集合的排列。 –

這使我困惑。我現在需要什麼？注意我編輯的問題 –

我錯了。現在我得到了你想要的。使用AurelioDeRosa的建議 – mishadoff

當我看到這應該很好地工作：

concatMap（λA - > concatMap（λB - > concatMap（ λC - >（A，b，C））L3）L2）L1

其中concatMap（在C＃稱爲的SelectMany）被定義爲

concatMap FL =的concat（地圖FL）。

和地圖功能映射在一個列表

和CONCAT（有時也稱爲壓平）採用清單列表，並把它變成一個平坦的列表

來源

2016-05-23 10:49:16

多個陣列的笛卡爾乘積

回答

相關問題