2011-10-30 21 views
0

基本的には簡単な問題だと思いますが、私は固執しています。私の脳はこの問題によってブロックされているので、私があなたを助けてくれることを願っています。複数配列のデカルト積

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

は、今私は

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

のように、すべてのposibillityとINT [N]の配列を含むリストを持つようにしたいよう 私はそこにある、整数のNアレイに2を持っている6 * 5 * 3(90)個の要素があります。

これを行う簡単なアルゴリズムはありますか?私は言語が問題ではないと思うが、私はJavaを好む。

+4

に変換します。このキーワードでgoogleを試してみてください。 –

+1

ここでhttp://stackoverflow.com/questions/1140164/scala-can-yield-be-used-multiple-times-with-a-for-loop/5177163#5177163は、Scalaの短い再帰的なソリューションです。 –

+0

@userunknown申し訳ありませんが、私はそれを読むことができませんでした... Scalaは奇妙にあり、私はそれで働いたことはない...他の再帰的な解決策は、あなたがここにnumpyのを使用してPythonの実装を見つけることができます –

答えて

1

ヘルプのための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; 
    } 
} 
-1

私はあなたが望むものを理解するので、すべての順列を取得する必要があります。

再帰アルゴリズム、詳細hereを使用してください。

+0

私はOPが2からNのデカルト積を求めていると思う与えられた集合の順列ではなく、集合である。 –

+0

これは私を混乱させる。私は今何が必要ですか?私は質問を編集しました。 –

+0

私は間違っていました。今私はあなたが望むものを手に入れました。 AurelioDeRosaのアドバイスを使用する – mishadoff

0

私はこれが正常に動作する必要があります見ての通り: - > concatMap(λB - > concatMap(

concatMapを(λA私もそれが一般的なので、uは任意のオブジェクト上の任意の直積集合だけでなく、int型を持つことができませんλC - >(A、B、C))L3)、L2)L1 concatMap(C#でSelectManyと呼ばれる)は

concatMap FL =連結(マップFL)として定義される

とマップリスト

と連結上の機能をマップするには、(時にはフラット化と呼ばれる)のリストのリストを取り、あなたが「デカルト積アルゴリズム」を検索しているフラットリスト

関連する問題