Geek asks and answers

How many different sequences, that the difference between each adjacent pair of numbers is greater than 1

I just find a problem like this

"Give you N different integers, do you know how many different sequences differ from each adjacent pair of numbers greater than 1?"

And when the integers are "1 2 3", then the answer is zero, when the integers are "5 3 1", then the answer is 6, for "1 3 5" "1 5 3" "3 1 5" "3 5 1" "5 1 3" "5 3 1" satisfies the problem, I just tried everything I could, but I could not solve it, so my question is how to write an algorithm to solve it.

Thankyou.

Here is my program

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;
}
+3
source share
3 answers

" ..." . , 25! 1.55 x 10 ^ 24, , . .

, . . http://en.wikipedia.org/wiki/Combinatorics , , http://en.wikipedia.org/wiki/Combinations .

0

, " " .

:

(+ -1 ). C (N, N div 2).

(). Multiply .

: :

FullSet = (A, B, C, D) , A, (B, C, D) A, , A. , B ...

. .

memoization [InitialValue, Set] ( ). .

, , - , memoization.

- O (N ^ 2 * 2 ^ N), O (N * 2 ^ N), () 2 ^ N . , N <= 20 ( Int64 Count).

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

0

To find a solution faster than the O (n!) Method, listing all the permutations and checking them, notice that this problem is an instance of counting all the Hamiltonian paths on the graph (V, E), where V are the members of the original list and E the edges connecting elements that may be adjacent. (So ​​your second example would be V = {1,3,5} and E = {(1,3), (3,5), (1,5)}.)

I do not know how you could efficiently calculate the Hamiltonian paths, but perhaps this is a solution.

0
source

More articles:


All Articles