3

私はちょうどこのような問題を見つけます

「N 個の異なる整数を与えてください。隣接するすべての数値のペアの差が 1 より大きい異なる数列がいくつあるか知っていますか?」

そして、整数が「1 2 3」の場合、答えは 0、整数が「5 3 1」の場合、答えは 6、「1 3 5」「1 5 3」「3 1 5」の場合3 5 1" "5 1 3" "5 3 1" は問題を満たしています。できることはすべて試しましたが解決できませんでした。私の質問は、それを解決するアルゴリズムをどのように書くかです。

ありがとうございました。

これが私のプログラムです

int n;bool vi[30];int a[30];int b[30];int counter = 0;
void dfs(int k)
{
    if ( k == n)
    {
        for (int i = 2; i <= n; i ++)
            if (fabs(b[i] - b[i - 1]) <= 1) return ;
        counter ++;
        return ;
    }
    for (int i = 0; i < n; i ++)
    {
    if (!vi[i])
    {
        b[k + 1] = a[i];
        vi[i] = true;
        dfs(k + 1);
        vi[i] = false;
        }
    }
}
int main (void)
{
        cin >> n;
        for (int i = 0; i < n; i ++)
            cin >> a[i];
        memset(vi, 0, sizeof(vi));
        for (int i = 0; i < n; i ++)
        {
            vi[i] = true;b[1] = a[i];dfs(1);vi[i] = false;
        }
        cout << counter << endl;
    return 0;
}
4

3 に答える 3

0

「いくつの異なるシーケンスがあるか...」という質問に対する答えは、すべての組み合わせを列挙しなくても解決できます。約 1.55 x 10^24、または既存のコンピューターが 1 秒間に列挙する25!よりもはるかに大きいため、これは良いことです。または1年で。

これは数学の問題、特に組合せ論です。問題を解決する方法については、http://en.wikipedia.org/wiki/Combinatorics と、場合によっては http://en.wikipedia.org/wiki/Combinations を参照してください。

于 2012-04-24T13:07:01.050 に答える
0

「ミート・イン・ザ・ミドル」の原則により、妥当な作業時間が得られるようです。

スケッチ：

数値リストを等分に分割します (長さが奇数の場合は +-1)。C(N, N div 2) バリアントがあります。

すべての固定された最後の要素と最初の要素について、前半と後半の有効な順列の数を (再帰的に) 計算します。互換性のある最後の要素と最初の要素のカウントを乗算します。

編集:より信頼性の高いバリアントが見つかりました:

Let's FullSet = (A, B, C, D) A から始まる有効な順列を計算するには、A と互換性のある値から始まる、A のないセット (B, C, D) の有効な順列をカウントする必要があります。同じことが当てはまります。 Bなどで始まる有効な順列の場合...

最初に、すべての初期値にアクセスし、これらの値のないセットの有効な順列をカウントする再帰関数を作成しました。小規模なセットのみに適しています。

次に、メモ化を使用して、組み合わせ [InitialValue, Set] のカウントを記憶しました (同じセットの計算を繰り返さないようにするため)。これがアップダウン動的計画法です。

最後に、動的プログラミングをアップダウン スタイルから昇順スタイルに変換しました。これは、メモ化テーブルを順番に埋めることができるため可能です。

複雑さは O(N^2 * 2^N) であり、メモリ消費は O(N * 2^N) です。これは、完全なセットの 2^N サブセットすべてを (ほぼ) 調べる必要があるためです。したがって、このメソッドを N <= 20 に使用できます (Count に Int64 型で十分な場合)。

Delphi コード:

var
  A: TArray<Byte>;
  Memo: array of array of Int64;
  N, Mask, msk, index, i: Integer;
  Count: Int64;
  OnlyOneOneBit: Boolean;

begin
  A := TArray<Byte>.Create(1, 2, 4, 5);

  N := Length(A);
  Mask := (1 shl N) - 1;//binary 000111111 with n ones

  SetLength(Memo, 1 shl N {2^N}, N);

  for msk := 1 to Mask do begin // all possible subsets, excluding empty one
    OnlyOneOneBit := 0 = (msk and (msk - 1));
    for index := 0 to N - 1 do
       if OnlyOneOneBit then
         Memo[msk, index] := (msk shr index) and 1 // 1 if indexth bit = 1 else 0
       else if 0 <> ((msk shr index) and 1) then begin
         Count := 0;
         for i := 0 to N - 1 do
           if Abs(A[i] - A[index]) > 1 then //compatible numbers
              Count := Count + Memo[msk xor (1 shl index), i];
     //use previous result for the set without index element, starting with ith
         Memo[msk, index] := Count;
       end;
  end;

  Count := 0;
  for index := 0 to N - 1 do
    Count := Count + Memo[Mask, index];

使用例 (1、2、4、5) の結果は 8 です ハンドチェック: 1425 1524 2415 2514 4152 4251 5142 5241

于 2012-04-24T13:29:48.560 に答える
0

すべての順列を列挙してチェックする O(n!) アプローチよりも速く解を見つけるために、この問題はグラフ (V, E) 上のすべてのハミルトニアン パスをカウントするインスタンスであることに注意してください。ここで、V は元のリストのメンバーと E は、隣接できるメンバーを接続するエッジです。(したがって、2 番目の例は V={1,3,5} および E={(1,3),(3,5),(1,5)} になります。)

ハミルトニアン パスを効率的にカウントする方法はわかりませんが、おそらくそれが解決策です。

于 2012-04-24T17:07:03.387 に答える