8

0, 1, ..., (N - 1)番号を順番に読んでいます。O(1)私の目標は、スペースのみを使用して、この特定の順列の辞書編集インデックスを見つけることです。

この質問は以前に尋ねられましたが、私が見つけたすべてのアルゴリズムは使用済みO(N)スペースです。それは不可能だと思い始めています。しかし、それは割り当ての数を減らすのに本当に役立ちます。

4

7 に答える 7

4

次のデータを考慮します。

chars = [a, b, c, d]
perm = [c, d, a, b]
ids = get_indexes(perm, chars) = [2, 3, 0, 1]

繰り返しによる順列の可能な解決策は次のとおりです。

len = length(perm)         (len = 4)
num_chars = length(chars)  (len = 4)

base = num_chars ^ len     (base = 4 ^ 4 = 256)
base = base / len          (base = 256 / 4 = 64)

id = base * ids[0]         (id = 64 * 2 = 128)
base = base / len          (base = 64 / 4 = 16)

id = id + (base * ids[1])  (id = 128 + (16 * 3) = 176)
base = base / len          (base = 16 / 4 = 4)

id = id + (base * ids[2])  (id = 176 + (4 * 0) = 176)
base = base / len          (base = 4 / 4 = 1)

id = id + (base * ids[3])  (id = 176 + (1 * 1) = 177)

逆のプロセス：

id = 177
(id / (4 ^ 3)) % 4 = (177 / 64) % 4 =   2 % 4 = 2 -> chars[2] -> c
(id / (4 ^ 2)) % 4 = (177 / 16) % 4 =  11 % 4 = 3 -> chars[3] -> d
(id / (4 ^ 1)) % 4 = (177 / 4)  % 4 =  44 % 4 = 0 -> chars[0] -> a
(id / (4 ^ 0)) % 4 = (177 / 1)  % 4 = 177 % 4 = 1 -> chars[1] -> b

可能な順列の数は、可能な文字の数、および順列の桁数num_chars ^ num_perm_digitsとして、によって与えられます。num_charsnum_perm_digits

これにはO(1)、初期リストを一定のコストと見なして、スペースが必要です。そして、あなたの順列が持つ桁数をO(N)考えると、それは時間内に必要です。N

上記の手順に基づいて、次のことができます。

function identify_permutation(perm, chars) {

    for (i = 0; i < length(perm); i++) {
        ids[i] = get_index(perm[i], chars);
    }

    len = length(perm);
    num_chars = length(chars);

    index = 0;
    base = num_chars ^ len - 1;
    base = base / len;
    for (i = 0; i < length(perm); i++) {
        index += base * ids[i];
        base = base / len;
    }

}

これは擬似コードですが、任意の言語に変換するのも非常に簡単です（：

于 2012-12-23T18:13:11.663 に答える
3

順列の代わりに辞書式インデックスまたは一意の組み合わせのランクを取得する方法を探している場合、問題は二項係数に該当します。二項係数は、合計N個のアイテムを持つKのグループで一意の組み合わせを選択する問題を処理します。

二項係数を操作するための一般的な関数を処理するクラスをC＃で作成しました。次のタスクを実行します。

  1. すべてのKインデックスを、任意のN選択Kのファイルに適切な形式で出力します。Kインデックスは、より説明的な文字列または文字に置き換えることができます。

  2. Kインデックスを、ソートされた二項係数テーブルのエントリの適切な辞書式インデックスまたはランクに変換します。この手法は、反復に依存する以前に公開された手法よりもはるかに高速です。これは、パスカルの三角形に固有の数学的プロパティを使用してこれを行い、セットを反復処理する場合に比べて非常に効率的です。

  3. ソートされた二項係数テーブルのインデックスを対応するKインデックスに変換します。また、古い反復ソリューションよりも高速であると思います。

  4. マークドミナス法を使用して二項係数を計算します。二項係数はオーバーフローする可能性がはるかに低く、より大きな数値で機能します。

  5. このクラスは.NETC＃で記述されており、ジェネリックリストを使用して問題に関連するオブジェクト（存在する場合）を管理する方法を提供します。このクラスのコンストラクターは、InitTableと呼ばれるbool値を取ります。これは、trueの場合、管理対象のオブジェクトを保持するためのジェネリックリストを作成します。この値がfalseの場合、テーブルは作成されません。上記の4つの方法を使用するために、テーブルを作成する必要はありません。テーブルにアクセスするためのアクセサメソッドが提供されています。

  6. クラスとそのメソッドの使用方法を示す関連するテストクラスがあります。2つのケースで広範囲にテストされており、既知のバグはありません。

このクラスについて読んでコードをダウンロードするには、二項係数の表化を参照してください。

次のテスト済みコードは、それぞれの固有の組み合わせを繰り返し処理します。

public void Test10Choose5()
{
   String S;
   int Loop;
   int N = 10;  // Total number of elements in the set.
   int K = 5;  // Total number of elements in each group.
   // Create the bin coeff object required to get all
   // the combos for this N choose K combination.
   BinCoeff<int> BC = new BinCoeff<int>(N, K, false);
   int NumCombos = BinCoeff<int>.GetBinCoeff(N, K);
   // The Kindexes array specifies the indexes for a lexigraphic element.
   int[] KIndexes = new int[K];
   StringBuilder SB = new StringBuilder();
   // Loop thru all the combinations for this N choose K case.
   for (int Combo = 0; Combo < NumCombos; Combo++)
   {
      // Get the k-indexes for this combination.  
      BC.GetKIndexes(Combo, KIndexes);
      // Verify that the Kindexes returned can be used to retrive the
      // rank or lexigraphic order of the KIndexes in the table.
      int Val = BC.GetIndex(true, KIndexes);
      if (Val != Combo)
      {
         S = "Val of " + Val.ToString() + " != Combo Value of " + Combo.ToString();
         Console.WriteLine(S);
      }
      SB.Remove(0, SB.Length);
      for (Loop = 0; Loop < K; Loop++)
      {
         SB.Append(KIndexes[Loop].ToString());
         if (Loop < K - 1)
            SB.Append(" ");
      }
      S = "KIndexes = " + SB.ToString();
      Console.WriteLine(S);
   }
}

このクラスは、選択した言語にかなり簡単に移植できるはずです。目標を達成するために、クラスの一般的な部分を移植する必要はおそらくないでしょう。使用している組み合わせの数によっては、4バイトintよりも大きいワードサイズを使用する必要がある場合があります。

于 2012-12-24T04:32:36.047 に答える
1

geekviewpointには、この問題に対するJavaソリューションがあります。なぜそれが真実であり、コードが簡単に理解できるのかについての良い説明があります。http://www.geekviewpoint.com/java/numbers/permutation_index。また、さまざまな入力でコードを実行する単体テストもあります。

于 2012-12-24T16:32:54.347 に答える
0

Nあります！順列。インデックスを表すには、少なくともNビットが必要です。

于 2012-12-23T18:20:14.803 に答える
0

算術演算が定数時間であると想定したい場合は、次の方法があります。

def permutationIndex(numbers):
  n=len(numbers)
  result=0
  j=0
  while j<n:
    # Determine factor, which is the number of possible permutations of
    # the remaining digits.
    i=1
    factor=1
    while i<n-j:
      factor*=i
      i+=1
    i=0
    # Determine index, which is how many previous digits there were at
    # the current position.
    index=numbers[j]
    while i<j:
      # Only the digits that weren't used so far are valid choices, so
      # the index gets reduced if the number at the current position
      # is greater than one of the previous digits.
      if numbers[i]<numbers[j]:
        index-=1
      i+=1
    # Update the result.
    result+=index*factor
    j+=1
  return result

Pythonの組み込み操作を使用してより簡単に実行できる特定の計算を意図的に書きましたが、余分な非定数のスペースが使用されていないことをより明確にしたいと思いました。

maxim1000が指摘したように、結果を表すために必要なビット数はnが増加するにつれて急速に増加するため、最終的には大きな整数が必要になり、一定時間の演算がなくなりますが、このコードはあなたの質問の精神に対応していると思います。

于 2012-12-23T19:24:59.907 に答える
0

アイデアに本当に新しいものはありませんが、明示的なループや再帰のない完全にマトリックス的な方法です（Numpyを使用していますが、簡単に適応できます）。

import numpy as np
import math
vfact = np.vectorize(math.factorial, otypes='O')

def perm_index(p):
    return np.dot( vfact(range(len(p)-1, -1, -1)),
                   p-np.sum(np.triu(p>np.vstack(p)), axis=0) )
于 2016-09-18T14:25:28.100 に答える
0

Visual Basicを使用してコードを記述したところ、プログラムは17要素までの特定のインデックスに対するすべてのインデックスまたは対応するすべての順列を直接計算できます（この制限は、コンパイラの17を超える数値の科学的記数法の近似によるものです）。

興味があれば、プログラムを送信するか、ダウンロード用にどこかに公開することができます。これは正常に機能し、コードの出力をテストしてパラゴン化するのに役立ちます。

私は階乗進法と呼ばれるJamesD.McCaffreyの方法を使用しました。これについては、こことここでも読むことができます（ページの最後の説明で）。

于 2016-09-24T16:28:50.137 に答える