0

可変数のリストがあります。それぞれに異なる数の要素が含まれています。

たとえば、4 つのリストの場合、

array1 = {1, 2, 3, 4};
array2 = {a, b, c};
array3 = {X};
array4 = {2.10, 3.5, 1.2, 6.2, 0.3};

{1,a,X,2.10}、{1,a,X,3.5} など、i 番目の要素が i 番目のリストからのものである可能性のあるすべてのタプルを見つける必要があります。

現在、パフォーマンスの問題がある再帰的な実装を使用しています。したがって、より高速に実行できる非反復的な方法を見つけたいと思います。

何かアドバイス？効率的なアルゴリズム (または疑似コード) はありますか。ありがとう！

これまでに実装したもののいくつかの擬似コード:

再帰的なバージョン:

vector<size_t> indices; // store current indices of each list except for the last one)

permuation (index, numOfLists) { // always called with permutation(0, numOfLists)
  if (index == numOfLists - 1) {
    for (i = first_elem_of_last_list; i <= last_elem_of_last_list; ++i) {
      foreach(indices.begin(), indices.end(), printElemAtIndex());
      printElemAtIndex(last_list, i);
    }
  }
  else {
    for (i = first_elem_of_ith_list; i <= last_elem_of_ith_list; ++i) {
      update_indices(index, i);
      permutation(index + 1, numOfLists); // recursive call
    }
  }
}

非再帰バージョン:

vector<size_t> indices; // store current indices of each list except for the last one)
permutation-iterative(index, numOfLists) {
  bool forward = true;
  int curr = 0;

  while (curr >= 0) {
    if (curr < numOfLists - 1){
      if (forward) 
        curr++;
      else {
        if (permutation_of_last_list_is_done) {
          curr--;
        }
        else {
          curr++;
          forward = true;
        }
        if (curr > 0) 
          update_indices();
      }
    }
    else {
      // last list
      for (i = first_elem_of_last_list; i <= last_elem_of_last_list; ++i) {
        foreach(indices.begin(), indices.end(), printElemAtIndex());
        printElemAtIndex(last_list, i);
      }
      curr--;
      forward = false;
    }
  }
}
4

1 に答える 1

3

はO(l^n)リストlのサイズ、 はリストのn数です。

したがって、それらすべてを多項式で効率的に生成することはできません。

いくつかの局所的な最適化を行うことができるかもしれませんが、特に反復バージョンがスタック + ループを使用して再帰ソリューションを模倣しようとしている場合は、反復バージョンと (効率的な) 再帰バージョンの間で切り替えを行っても大きな違いが生じるとは思えません。ハードウェア スタックほど最適化されていない可能性があります。

可能な再帰的アプローチは次のとおりです。

printAll(list<list<E>> listOfLists, list<E> sol):
  if (listOfLists.isEmpty()):
      print sol
      return
  list<E> currentList <- listOfLists.removeAndGetFirst()
  for each element e in currentList:
      sol.append(e)
      printAll(listOfLists, sol) //recursively invoking with a "smaller" problem
      sol.removeLast()
  listOfLists.addFirst(currentList)

(1) 正確にはl1 * l2 * ... * ln、li が i 番目のリストのサイズであるタプルがあります。同じ長さのリストの場合、 に減衰しl^nます。

于 2012-12-05T09:21:14.020 に答える