복붙노트

다른 사람을 계산하지 않고 n 번째 순열 찾기

PHP

다른 사람을 계산하지 않고 n 번째 순열 찾기

순열 원자를 나타내는 N 요소의 배열이 주어지면, 그와 같은 알고리즘이 존재합니다 :

function getNthPermutation( $atoms, $permutation_index, $size )

여기서 $ atoms는 원소들의 배열이고, $ permutation_index는 순열의 인덱스이고 $ size는 순열의 크기입니다.

예를 들면 :

$atoms = array( 'A', 'B', 'C' );
// getting third permutation of 2 elements
$perm = getNthPermutation( $atoms, 3, 2 );

echo implode( ', ', $perm )."\n";

인쇄할까요?

B, A

$ permutation_index까지 모든 순열을 계산하지 않고?

나는 factoradic 순열에 대해 들었지만, 모든 구현은 결과가 동일한 경우 V가 아닌 순열을 제공합니다. 이는 제 경우가 아닙니다.

감사.

해결법

  1. ==============================

    1.RickyBobby가 말했듯이, 순열의 사전 식 순서를 고려할 때, 당신은 당신의 이점으로 계승 분해를 사용해야합니다.

    RickyBobby가 말했듯이, 순열의 사전 식 순서를 고려할 때, 당신은 당신의 이점으로 계승 분해를 사용해야합니다.

    실용적인 관점에서 볼 때 이것이 내가 보는 방법이다.

    다음의 C 코드는 이것이 어떻게 작동 하는지를 알려줄 것입니다 (n은 엔트리의 수이고 i는 순열의 인덱스입니다) :

    /**
 * @param n The number of entries
 * @param i The index of the permutation
 */
void ithPermutation(const int n, int i)
{
   int j, k = 0;
   int *fact = (int *)calloc(n, sizeof(int));
   int *perm = (int *)calloc(n, sizeof(int));

   // compute factorial numbers
   fact[k] = 1;
   while (++k < n)
      fact[k] = fact[k - 1] * k;

   // compute factorial code
   for (k = 0; k < n; ++k)
   {
      perm[k] = i / fact[n - 1 - k];
      i = i % fact[n - 1 - k];
   }

   // readjust values to obtain the permutation
   // start from the end and check if preceding values are lower
   for (k = n - 1; k > 0; --k)
      for (j = k - 1; j >= 0; --j)
         if (perm[j] <= perm[k])
            perm[k]++;

   // print permutation
   for (k = 0; k < n; ++k)
      printf("%d ", perm[k]);
   printf("\n");

   free(fact);
   free(perm);
}

    예를 들어, ithPermutation (10, 3628799)은 예상대로 10 개 요소의 마지막 순열을 인쇄합니다.

    9 8 7 6 5 4 3 2 1 0
  2. ==============================

    2.순열의 크기를 선택할 수있는 솔루션이 있습니다. 예를 들어, 10 요소의 모든 순열을 생성 할 수 있다는 것 말고는, 10 요소 중 쌍의 순열을 생성 할 수 있습니다. 또한 정수가 아닌 임의의 객체 목록을 변환합니다.

    순열의 크기를 선택할 수있는 솔루션이 있습니다. 예를 들어, 10 요소의 모든 순열을 생성 할 수 있다는 것 말고는, 10 요소 중 쌍의 순열을 생성 할 수 있습니다. 또한 정수가 아닌 임의의 객체 목록을 변환합니다.

    이것은 PHP이지만 JavaScript와 Haskell 구현도 있습니다.

    function nth_permutation($atoms, $index, $size) {
    for ($i = 0; $i < $size; $i++) {
        $item = $index % count($atoms);
        $index = floor($index / count($atoms));
        $result[] = $atoms[$item];
        array_splice($atoms, $item, 1);
    }
    return $result;
}

    사용 예 :

    for ($i = 0; $i < 6; $i++) {
    print_r(nth_permutation(['A', 'B', 'C'], $i, 2));
}
// => AB, BA, CA, AC, BC, CB

    어떻게 작동합니까?

    그 뒤에 매우 흥미로운 아이디어가 있습니다. A, B, C, D의 목록을 가져와 봅시다. 우리는 카드 덱 에서처럼 요소를 그려서 순열을 만들 수 있습니다. 처음에는 네 가지 요소 중 하나를 그릴 수 있습니다. 마지막으로 우리는 아무것도 남지 않을 때까지 남은 세 가지 요소 중 하나입니다.

    가능한 선택 순서는 다음과 같습니다. 위로부터 시작하여 세 번째 경로를 취한 다음 첫 번째 경로, 두 번째 경로 및 마지막 경로를 취합니다. 이것이 우리의 순열 13 번입니다.

    이 선택 순서에 따라 알고리즘 적으로 13 번째 숫자를 얻는 방법을 생각해보십시오. 그런 다음 알고리즘을 바꾸면 정수에서 시퀀스를 재구성 할 수 있습니다.

    선택의 연속을 중복하지 않고 정수로 채우고 다시 압축을 푸는 일반적인 방법을 찾으려고합니다.

    하나의 흥미로운 체계를 10 진수 시스템이라고합니다. "27"은 10 번 중 2 번 경로를 선택한 다음 10 번 중 7 번 경로를 선택하는 것으로 생각할 수 있습니다.

    그러나 각 자릿수는 10 가지 대안 중에서 선택할 수 있습니다. 2 진수 및 16 진수와 같이 고정 기수를 사용하는 다른 시스템은 고정 된 수의 대체 항목 중에서 선택 시퀀스 만 인코딩 할 수도 있습니다. 우리는 가변 기수, 시간 단위와 같은 종류의 시스템을 원합니다. "14:05:29"는 24 시간 14 분, 60 분 5 분, 60 분 29 초입니다.

    일반적인 number-to-string 및 string-to-number 함수를 사용하여 혼합 된 기수를 사용하여 속일 경우 어떻게됩니까? parseInt ( 'beef', 16) 및 (48879) .toString (16)과 같은 단일 기수를 사용하는 대신 각 자리에 하나의 기수를 사용합니다.

    function pack(digits, radixes) {
    var n = 0;
    for (var i = 0; i < digits.length; i++) {
        n = n * radixes[i] + digits[i];
    }
    return n;
}

function unpack(n, radixes) {
    var digits = [];
    for (var i = radixes.length - 1; i >= 0; i--) {
        digits.unshift(n % radixes[i]);
        n = Math.floor(n / radixes[i]);
    }
    return digits;
}

    심지어 작동합니까?

    // Decimal system
pack([4, 2], [10, 10]); // => 42

// Binary system
pack([1, 0, 1, 0, 1, 0], [2, 2, 2, 2, 2, 2]); // => 42

// Factorial system
pack([1, 3, 0, 0, 0], [5, 4, 3, 2, 1]); // => 42

    그리고 지금 뒤로 :

    unpack(42, [10, 10]); // => [4, 2]

unpack(42, [5, 4, 3, 2, 1]); // => [1, 3, 0, 0, 0]

    이것은 너무 아름답습니다. 지금이 순열의 문제에이 파라 메트릭 숫자 체계를 적용 해보자. 우리는 A, B, C, D의 길이 2 순열을 고려할 것입니다. 이들의 총 수는 얼마입니까? 봅시다. 먼저 4 개의 아이템 중 하나를 그리고 나머지 3 개의 아이템 중 하나를 그립니다. 2 아이템을 그리는 방법은 4 * 3 = 12 가지입니다. 이 12 가지 방법은 정수로 묶일 수 있습니다 [0.11]. 자, 이미 포장 한 것으로 가정하고 포장 풀기를 시도하십시오.

    for (var i = 0; i < 12; i++) {
    console.log(unpack(i, [4, 3]));
}

// [0, 0], [0, 1], [0, 2],
// [1, 0], [1, 1], [1, 2],
// [2, 0], [2, 1], [2, 2],
// [3, 0], [3, 1], [3, 2]

    이 숫자는 원래 배열의 인덱스가 아니라 선택 항목을 나타냅니다. [0, 0]은 A, B, C, D (A) 항목에서 나머지 항목 B, C, D (B 항목)에서 항목 # 0을 취하는 것을 의미합니다. . 그리고 결과 순열은 A, B입니다.

    또 다른 예 : [3, 2]는 나머지 목록 A, B, C (즉 C)에서 A, B, C, D (즉 D) 항목 다음에 항목 # 2를 가져 오는 것을 의미합니다. 그리고 결과 순열은 D, C입니다.

    이 매핑을 Lehmer 코드라고합니다. 이 모든 Lehmer 코드를 순열에 매핑 해 봅시다 :

    AB, AC, AD, BA, BC, BD, CA, CB, CD, DA, DB, DC

    그것이 바로 우리가 필요로하는 것입니다. 그러나 언팩 (unpack) 기능을 살펴보면 오른쪽에서 왼쪽으로 숫자가 생성됨을 알 수 있습니다 (팩의 동작을 되돌리기 위해). 3에서부터 선택은 4에서 선택하기 전에 언팩됩니다. 3에서 선택하기 전에 4 개의 요소 중에서 선택하기를 원하기 때문에 불행합니다. 그렇게 할 수 없으면 먼저 Lehmer 코드를 계산하여 임시 배열에 축적해야합니다. 그런 다음 실제 순열을 계산하기 위해 항목 배열에 적용합니다.

    그러나 사전 식 순서에 신경 쓰지 않는다면 우리는 4 가지 중에서 선택하기 전에 3 가지 요소 중에서 선택하고 싶은 척할 수 있습니다. 그런 다음 4 번부터 선택하면 가장 먼저 압축이 풀립니다. 즉, unpack (n, [4, 3]) 대신에 unpack (n, [3, 4])을 사용합니다. 이 트릭을 사용하여 Lehmer 코드의 다음 자릿수를 계산하고 즉시 목록에 적용 할 수 있습니다. 그리고 그것이 정확히 nth_permutation ()이 작동하는 방법입니다.

    마지막으로 언급하고자하는 것은 unpack (i, [4, 3])이 팩토리얼 번호 시스템과 밀접한 관련이 있다는 것입니다. 첫 번째 트리를 다시보십시오. 중복없이 길이 2의 순열을 원한다면 매 두 번째 순열 인덱스를 건너 뛸 수 있습니다. 길이가 4 인 12 개의 순열을 얻을 수 있습니다. 길이는 길이 2로 조정할 수 있습니다.

    for (var i = 0; i < 12; i++) {
    var lehmer = unpack(i * 2, [4, 3, 2, 1]); // Factorial number system
    console.log(lehmer.slice(0, 2));
}
  3. ==============================

    3.그것은 당신의 순열을 "정렬"하는 방식에 달려 있습니다 (예를 들어 사전 식 순서).

    그것은 당신의 순열을 "정렬"하는 방식에 달려 있습니다 (예를 들어 사전 식 순서).

    그것을 행하는 한 가지 방법은 계승 수 체계입니다. [0, n!]과 모든 순열 사이의 순환을 제공합니다.

    그런 다음 [0, n!]에있는 숫자 i에 대해 다른 것들을 계산하지 않고 i 번째 순열을 계산할 수 있습니다.

    이 계승 작성은 [0과 n!] 사이의 숫자는 다음과 같이 쓸 수 있다는 사실에 기반합니다 :

    SUM( ai.(i!) for i in range [0,n-1]) where ai <i

    (베이스 분해와 꽤 유사합니다)

    이 분해에 대한 자세한 내용은이 스레드를 살펴보십시오. https://math.stackexchange.com/questions/53262/factorial-decomposition-of-integers

    도움이되기를 바랍니다.

    이 위키피디아 기사에서 언급했듯이이 접근법은 lehmer 코드를 계산하는 것과 같습니다.

    따라서 n 요소 집합에 대해 할 수있는 최선의 방법은 적응 된 데이터 구조를 갖는 O (n ln (n))입니다.

  4. ==============================

    4.다음은 순열과 랭크를 선형 시간으로 변환하는 알고리즘입니다. 그러나 순위는 사전 편집이 아닙니다. 이상하지만 일관성이 있습니다. 저는 두 가지 함수, 즉 랭크 (rank)에서 순열 (permutation)로 변환하는 함수와 역함수 (inverse)를 수행하는 함수를 제공 할 것입니다.

    다음은 순열과 랭크를 선형 시간으로 변환하는 알고리즘입니다. 그러나 순위는 사전 편집이 아닙니다. 이상하지만 일관성이 있습니다. 저는 두 가지 함수, 즉 랭크 (rank)에서 순열 (permutation)로 변환하는 함수와 역함수 (inverse)를 수행하는 함수를 제공 할 것입니다.

    첫째, 무 순위 (순위에서 순열로 이동)

    Initialize:
n = length(permutation)
r = desired rank
p = identity permutation of n elements [0, 1, ..., n]

unrank(n, r, p)
  if n > 0 then
    swap(p[n-1], p[r mod n])
    unrank(n-1, floor(r/n), p)
  fi
end

    다음 순위 :

    Initialize:
p = input permutation
q = inverse input permutation (in linear time, q[p[i]] = i for 0 <= i < n)
n = length(p)

rank(n, p, q)
  if n=1 then return 0 fi
  s = p[n-1]
  swap(p[n-1], p[q[n-1]])
  swap(q[s], q[n-1])
  return s + n * rank(n-1, p, q)
end

    이 둘의 실행 시간은 O (n)입니다.

    왜 이렇게 작동 하는지를 설명하는 훌륭한 읽을 거리가있는 종이가 있습니다 : Myrvold & Ruskey, 정보 처리 문서 79 권, 6 호, 2001 년 9 월 30 일, 281-284 페이지, 선형 시간의 순열 정렬 및 정렬 해제.

    http://webhome.cs.uvic.ca/~ruskey/Publications/RankPerm/MyrvoldRuskey.pdf

  5. ==============================

    5.다음은 요소의 목록 (아래 예제의 첫 번째 13 자)에 대해 작업하는 파이썬의 짧고 매우 빠른 (요소 수가 선형 인) 솔루션입니다.

    다음은 요소의 목록 (아래 예제의 첫 번째 13 자)에 대해 작업하는 파이썬의 짧고 매우 빠른 (요소 수가 선형 인) 솔루션입니다.

    from math import factorial

def nthPerm(n,elems):#with n from 0
    if(len(elems) == 1):
        return elems[0]
    sizeGroup = factorial(len(elems)-1)
    q,r = divmod(n,sizeGroup)
    v = elems[q]
    elems.remove(v)
    return v + ", " + ithPerm(r,elems)

    예 :

    letters = ['a','b','c','d','e','f','g','h','i','j','k','l','m']

ithPerm(0,letters[:])          #--> a, b, c, d, e, f, g, h, i, j, k, l, m
ithPerm(4,letters[:])          #--> a, b, c, d, e, f, g, h, i, j, m, k, l
ithPerm(3587542868,letters[:]) #--> h, f, l, i, c, k, a, e, g, m, d, b, j

    참고 :이 함수는 매개 변수 elems (선택한 요소 제거)를 수정하기 때문에 글자가 아닌 문자 [:] (문자 복사본)를 제공합니다.

  6. ==============================

    6.그것은 계산 가능합니다. 이것은 당신을 위해 그것을하는 C # 코드입니다.

    그것은 계산 가능합니다. 이것은 당신을 위해 그것을하는 C # 코드입니다.

    using System;
using System.Collections.Generic;

namespace WpfPermutations
{
    public class PermutationOuelletLexico3<T>
    {
        // ************************************************************************
        private T[] _sortedValues;

        private bool[] _valueUsed;

        public readonly long MaxIndex; // long to support 20! or less 

        // ************************************************************************
        public PermutationOuelletLexico3(T[] sortedValues)
        {
            if (sortedValues.Length <= 0)
            {
                throw new ArgumentException("sortedValues.Lenght should be greater than 0");
            }

            _sortedValues = sortedValues;
            Result = new T[_sortedValues.Length];
            _valueUsed = new bool[_sortedValues.Length];

            MaxIndex = Factorial.GetFactorial(_sortedValues.Length);
        }

        // ************************************************************************
        public T[] Result { get; private set; }

        // ************************************************************************
        /// <summary>
        /// Return the permutation relative to the index received, according to 
        /// _sortedValues.
        /// Sort Index is 0 based and should be less than MaxIndex. Otherwise you get an exception.
        /// </summary>
        /// <param name="sortIndex"></param>
        /// <param name="result">Value is not used as inpu, only as output. Re-use buffer in order to save memory</param>
        /// <returns></returns>
        public void GetValuesForIndex(long sortIndex)
        {
            int size = _sortedValues.Length;

            if (sortIndex < 0)
            {
                throw new ArgumentException("sortIndex should be greater or equal to 0.");
            }

            if (sortIndex >= MaxIndex)
            {
                throw new ArgumentException("sortIndex should be less than factorial(the lenght of items)");
            }

            for (int n = 0; n < _valueUsed.Length; n++)
            {
                _valueUsed[n] = false;
            }

            long factorielLower = MaxIndex;

            for (int index = 0; index < size; index++)
            {
                long factorielBigger = factorielLower;
                factorielLower = Factorial.GetFactorial(size - index - 1);  //  factorielBigger / inverseIndex;

                int resultItemIndex = (int)(sortIndex % factorielBigger / factorielLower);

                int correctedResultItemIndex = 0;
                for(;;)
                {
                    if (! _valueUsed[correctedResultItemIndex])
                    {
                        resultItemIndex--;
                        if (resultItemIndex < 0)
                        {
                            break;
                        }
                    }
                    correctedResultItemIndex++;
                }

                Result[index] = _sortedValues[correctedResultItemIndex];
                _valueUsed[correctedResultItemIndex] = true;
            }
        }

        // ************************************************************************
        /// <summary>
        /// Calc the index, relative to _sortedValues, of the permutation received
        /// as argument. Returned index is 0 based.
        /// </summary>
        /// <param name="values"></param>
        /// <returns></returns>
        public long GetIndexOfValues(T[] values)
        {
            int size = _sortedValues.Length;
            long valuesIndex = 0;

            List<T> valuesLeft = new List<T>(_sortedValues);

            for (int index = 0; index < size; index++)
            {
                long indexFactorial = Factorial.GetFactorial(size - 1 - index);

                T value = values[index];
                int indexCorrected = valuesLeft.IndexOf(value);
                valuesIndex = valuesIndex + (indexCorrected * indexFactorial);
                valuesLeft.Remove(value);
            }
            return valuesIndex;
        }

        // ************************************************************************
    }
}
  7. ==============================

    7.예를 들어 배열에 모든 순열을 메모리에 저장하면 O (1) 시간에 한 번에 하나씩 다시 가져올 수 있어야합니다.

    예를 들어 배열에 모든 순열을 메모리에 저장하면 O (1) 시간에 한 번에 하나씩 다시 가져올 수 있어야합니다.

    이것은 모든 순열을 저장해야한다는 것을 의미하므로 모든 순열을 계산하는 데 엄청난 시간이 걸리거나 저장하는 데 엄청난 공간이 필요하다면 이는 해결책이 아닐 수도 있습니다.

    어쨌든 시도해 보는 것이 좋을 것입니다. 너무 크거나 느린 경우 다시 돌아 오는 것이 좋습니다. 순진한 사람이 작업을 수행 할 경우 "영리한"해결책을 찾는 것이 중요하지 않습니다.

    8. from https://stackoverflow.com/questions/7918806/finding-n-th-permutation-without-computing-others by cc-by-sa and MIT license

'PHP' 카테고리의 다른 글

PHP에서 register_globals 란 무엇입니까?  (0) 2018.09.19
ajax 함수에 의해 호출 된 파일에 대한 직접 액세스 방지  (0) 2018.09.19
PHP 독서 shell_exec 라이브 출력  (0) 2018.09.19
쿠키가없는 PHP 세션  (0) 2018.09.19
PHP 세션 ID는 얼마나 독특한가요?  (0) 2018.09.19
,

티스토리툴바