Басқаларды есептемегенде n-th алмастыруды табу

Ұяшықтарды атомдардан тұратын 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 дейін әрбір орын алмастыруды есептемейсіз бе?

Мен факторадистік перестандарттар туралы бірдеңе естідім, бірақ табылған барлық іске асыру нәтижесі V сияқты бірдей өлшеммен алмастырады, бұл менің ісім емес.

Рахмет.

36
N-элементтердің әрбір орналастырылуын оның иерархиясының санауышымен басып шығаруды елестетіңіз (permutation 0, permutation 1, permutation 2, ...) ... n-th алмастыруды қалаймын.
қосылды автор Simone Margaritelli, көзі
Мен алмастыруларды сұрыптауға алаңдамаймын, кез-келген жұмыс жасайды :)
қосылды автор Simone Margaritelli, көзі
Егер тапсырысыңыз туралы қамқорлық жасамасаңыз, сіз қалаған $ мөлшерінің кез-келген түрін таңдауға болады. бұл функцияны әртүрлі индекспен әр рет бірнеше рет шақырғыңыз келе ме?
қосылды автор galchen, көзі
бірақ ауыстыру тәртібін анықтайды? Яғни, индексімен 0 орналасуы кез келген нысандар болуы мүмкін
қосылды автор galchen, көзі
Сізге ауыстыру индексі деген не?
қосылды автор galchen, көзі

7 жауаптар

RickyBobby мәлімдегендей, ауыспалы лексикографиялық тәртібін қарастырғанда, сіз фрактруктивті ыдырауды сіздің пайдаңызда пайдалануыңыз керек.

Практикалық тұрғыдан, мен оны көремін:

  • (n-1)! , (n-2)! ) бастап, форма сандарынан басқа, евклидтік бөлімдерді орындаңыз.
  • Кескіндерді массивке сақтаңыз. i - осы координат 0 және ni-1 код> 0 кодын n-1 .
  • Бұл массив - сіздің ауыстыруыңыз. Мәселе мынада, әр санат бұрынғы құндылықтарға көңіл бөлмейді, сондықтан оларды реттеу керек. Неғұрлым анық болса, әр мәнді неғұрлым төмен немесе тең болатын бұрынғы мәндер сияқты бірнеше есе ұлғайту қажет.

Төмендегі С коды сізге бұл қалай жұмыс істейтіні туралы түсінік беруі керек ( 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) күтілгендей, он элементтің соңғы орналасуы:

9 8 7 6 5 4 3 2 1 0
41
қосылды
+1 thx Feliks іске асыру үшін :)
қосылды автор Ricky Bobby, көзі
Бұл дәл іздеуді жүзеге асырғаным болды, 'n' дәлелі кілт ... рахмет soooo much :)
қосылды автор Simone Margaritelli, көзі
Бұл жерде қолданылатын әдіс, factoradic/lehmer кодын алу үшін (есептелетін факторларды пайдалануды және қалдықтарды сақтамайды) Wikipedia бетінен Factoradic мысалдар бөлімінен біраз жоғары. Мен тестілеуден өткен нәтиже бірдей болса да, соңғы әдісті қарапайым деп таптым. Дегенмен сіздің мысалыңыз маған тұжырымдаманы жақсырақ түсінуге көмектесті.
қосылды автор konsolebox, көзі

Мұнда орналастырудың өлшемін таңдауға мүмкіндік беретін шешім бар. Мысалы, 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 тізімін алайық. Біз карточкалардың палубасынан сияқты элементтерді сызу арқылы алмастыруды сала аламыз. Бастапқыда біз төрт элементтің бірін таңдай аламыз. Содан кейін қалған үш элементтердің бірі, және т.б., әзірге бізде ештеңе қалды.

Decision tree for permutations of 4 elements

Мүмкін таңдаудың кезекті тізбегі. Жоғарыдан бастап біз үшінші жолды алдық, содан кейін бірінші, екінші және соңында бірінші. Және бұл біздің № 13 орын.

Таңдаудың кезектілігін ескере отырып, он алгоритмдік санға қалай жетесіз делік. Содан кейін өзіңіздің алгоритміңізді кері қайтарыңыз, осылайша сіз бүтін саннан дәйектілікті қайта жасай аласыз.

Таңдаудың кезектілігін толығымен босатпастан орап алудың жалпы схемасын табуға тырысамыз және оны қайтадан ашамыз.

Бір қызықты сызба ондық сандар жүйесі деп аталады. «27» 10-дан 2-ші жолды таңдап, 10-дан # 7 жолды таңдай алады.

Decision three for number 27 in decimal

Бірақ әр таңбаны тек 10 баламадан таңдауға болады. Тіркелген радиоқабылдағыштар сияқты екілік және он алтылық секілді басқа жүйелерде баламалар санының белгілі бір санынан таңдау ғана мүмкін. Біз радиожиілігімен айнымалы жүйені, ұқсас уақыт бірліктерінің үлгісін, 14:05:29 сағат 14-тен 24-ке, 60-шы минуттың 5-іне дейін, 60-тан 29-шы орынға дейін.

Егер біз әдеттегі санды жолға және жолдан-сандыққа дейінгі функцияларды алсақ және оларды аралас радикамерлерді қолдануға мәжбүрлей алсақ? 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-нің бірі, яғни 4 * 3 = 12 2 элементті салу жолдары. Бұл 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, A параметрін қабылдау дегенді білдірмейді, ол A, B, C, D 0 қалған тізімнен B, C, D (бұл B). Сонда алынған ауысым A, B .

Тағы бір мысал: [3, 2] 3-тармақты A, B, C, D (яғни D) және одан кейінгі № 2 пункттен A, B, C (бұл C). Ал нәтиже алмасу D, C болып табылады.

Бұл картаға Lehmer коды деп аталады. Барлық Лехмер кодтарын перестандарттарға салыңыз:

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

Бұл бізге қажет нәрсе. Бірақ unpack функциясына қарасаңыз, ол солдан оңға қарай (« pack әрекеттерін қайтару үшін) сандарды шығаратындығын байқайсыз. Таңдау 3-тен 4-ке дейін таңдалғанға дейін шығарылады. Бұл бақытсыз, өйткені біз таңдағанға дейін 4 элементті таңдағымыз келеді. 3. Олай етпей, алдымен Лехер кодын есептеу керек, оны уақытша массивке жинақтап, содан кейін оны нақты алмастыруды есептеу үшін элементтердің жиынын қолданыңыз.

Бірақ біз лексикографиялық тәртіпті қамтымайтын болсақ, 4-тен таңдамас бұрын 3 элементтен таңдағымыз келетінін көрсете аламыз. Содан кейін 4-тен таңдау unpack алдымен шығарылады. Басқаша айтқанда 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));
}
25
қосылды

Бұл сіздің перестанцияларыңызды «сұрыптау» әдісіне байланысты (мысалы, лексикографиялық тапсырыс).

Мұны жүзеге асырудың бір жолы - фактуралық сандар жүйесі , ол сізге [0, n!] және барлық ауыстырулар.

Сонда [0, n!] Ішіндегі кез-келген сан үшін басқаларды есептемегенде алмастыруды есептеуге болады.

Бұл факторлық жазба [0 және n!] Арасындағы кез келген санды келесідей жазуға болады:

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

(бұл базалық ыдырауға өте ұқсас)

for more information on this decomposition, have a look at this thread : https://math.stackexchange.com/questions/53262/factorial-decomposition-of-integers

бұл көмектеседі деп үміттенемін


Бұл wikipedia мақаласында айтылғандай, бұл тәсіл lehmer code :

n перементтерін құрудың айқын жолы - құндылықтарды құру   Lehmer коды (фактруктивті сандар жүйесін пайдалану мүмкін   бүтін сандардың n-ға дейін ұсынылуы) және оларды айналдыру   тиісті ауыстыру. Алайда, соңғы қадам   өте тиімді, өйткені ол талап етіледі   n таңдаманың әрқайсысын тізбектеуден және оны жоюдан,   ерікті жағдайда; айқын көріністер   жиым ретінде немесе тізбектің тізбесі, екеуі де талап етеді (әр түрлі   себептері) туралы конверсияны орындау үшін n2/4 операциялар. С n   әдетте өте аз (әсіресе барлық ұрпақ болса)   ауыстыру қажет), бұл проблема көп емес, бірақ ол   бұл кездейсоқ және жүйелік ұрпақ үшін де пайда болады   айтарлықтай жақсартатын қарапайым баламалар. Осы себепті ол   арнайы емес, мүмкін болса да пайдалы болып көрінбейді   Лехмерден конверсияны жүзеге асыруға мүмкіндік беретін деректер құрылымы   O (n log n) уақытында ауыстыруға арналған код.

Осылайша n элементінің жиынтығы үшін жасай алатын ең жақсы амал O (n ln (n)) бейімделген деректер құрылымымен.

14
қосылды
@SimoneMargaritelli дегеніміз не? элементтің түпнұсқалық жинағының бір ішкі жиынын алмастыру керек пе?
қосылды автор Ricky Bobby, көзі
Мен фактorial сандар жүйесін білетінмін, бірақ шығу орнының өлшемі элементтердің бастапқы векторларының бірдей болмайтын нұсқаны таба алмаймын.
қосылды автор Simone Margaritelli, көзі
Сіз шынымен OE (n lg lg U) VEB ағаштарын пайдалана аласыз, себебі U = n. Төменгі шекара қандай?
қосылды автор dhruvbird, көзі

Міне, желілік уақыттарда перестандарттар мен қатарлар арасында айырбастау алгоритмі. Дегенмен, ол қолданатын рейтингісі лексикографиялық емес. Бұл қызықты, бірақ дәйекті. Мен екі функцияны бере аламын: бір дәрежеден ауысып, кері айналдырады.

Біріншіден, оқшауланбау (рангтан репутацияға өту)

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).

There's a nice, readable paper explaining why this works: Ranking & Unranking Permutations in Linear Time, by Myrvold & Ruskey, Information Processing Letters Volume 79, Issue 6, 30 September 2001, Pages 281–284.

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

7
қосылды
Бұл шешім, ең алдымен, ең жылдам болады, себебі сіз массивді қосуды (немесе элементін жоюды) орындаудың қажеті жоқ және +1 циклдары үшін кірістірілген жоқ.
қосылды автор James, көзі

Міне, питонда кез-келген элементтер тізімінде жұмыс істейтін қысқа және өте жылдам (элементтер санының желілік) шешімі (төменде келтірілген мысалда 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 параметрін өзгертетіндіктен, letters [:] ( letters көшірмесі)

4
қосылды
Егер тізімде қайталанатын таңбалар болса, не болды? Бұл дұрыс емес нәтиже.
қосылды автор Sonu Kumar, көзі

Егер барлық передатчиктерді жадта сақтасаңыз, мысалы массивте, оларды бір уақытта O (1) уақытында шығарып алуыңыз керек.

Бұл барлық перестанцияларды сақтау керек дегенді білдіреді, сондықтан егер барлық перестандарттарды есептеуге тыйым салынған ұзақ уақыт кетсе немесе оларды сақтау үлкен кеңістік болса, онда бұл шешім болмауы мүмкін.

Менің ұсынысым бәрібір оны сынап көріп, егер ол тым үлкен/баяу болса, қайтып келуі керек, егер ақылды адам жұмысын жасаса, «ақылды» шешім іздейді.

1
қосылды
Жақсы айтасыз, бұл сіз естуді ме? :) Бұл жай ғана түсінбеушілік болды, оны оңай дуэт алыңыз;)
қосылды автор Simone Margaritelli, көзі
Менің ойымша, бұл түсінікті болды, өйткені мен «... әрбір орын алмай есептелмей ...» ...
қосылды автор Simone Margaritelli, көзі
Егер мен бұл туралы сұрасам, алдын-ала жазылған переопределями арқылы сынап көргенмін ...
қосылды автор Simone Margaritelli, көзі
Қарсылама болмайды. Преамбулалық перестандарттарды пайдаланатын алгоритм кез-келген алмастыруды есептемейді. (Мен бұл мәселе мен басқа жауаптарды пайдалы деп таптым, өйткені мұнда ғанамын).
қосылды автор dansalmo, көзі
+1 сұрағаны үшін Симонаға жауап бермеді, бірақ ол шынымен сұраған сұраққа жауап берді.
қосылды автор Patrick87, көзі
Өкінішке орай, менің психикалық күш-жігерім бүгін мені бұзуы керек, немесе сіз бұл ақпаратты сіздің сұрағыңыздағы өте кішкентай мәтінге орналастырасыз.
қосылды автор Chris Browne, көзі
Сіз шын мәнінде «$ permutation_index дейін кез-келген орналастыруды есептемейсіз» деп жаздыңыз, ол «әр алмасуды есептемей» бірдей емес. Мен контекстен тыс өздері тырнақшасын алғаш рет көрген кезім!
қосылды автор Chris Browne, көзі
Aha, сіз мені ескі «тыныш» трюк қолданып жасадың. Енді жазған кез-келген жауабым мені ашуландырады, бұл менің беделімді теріс әсер етуі мүмкін! Ешқашан да, мен «жеңімпаз дәлелдер» туралы ештеңе айтқан жоқпын, нақты прогреске қол жеткізуге қызығушылық көп.
қосылды автор Chris Browne, көзі
Бұл екі жастағы жауап, бұл сұраққа жауаптар өте қанағаттанарлық, сондықтан өзімнің редакциялаудың қажеттілігін көрмеймін (егер бірдеңе болса, оны жоюға бейім болар едім). Сұрақ қоюға қатысты менің көзқарасым бұл күндер үшін, жазба үшін кішіпейіл әрі кешірімді болар еді. Менің ойымша, 2011 жылдың 27 қазанында жаман күн болдым.
қосылды автор Chris Browne, көзі

Бұл есептеледі. Бұл сіз үшін жасайтын C# коды.

using System;
using System.Collections.Generic;

namespace WpfPermutations
{
    public class PermutationOuelletLexico3
    {
       //************************************************************************
        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; }

       //************************************************************************
        /// 
/// 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. ///
 
        /// 
        /// 
Value is not used as inpu, only as output. Re-use buffer in order to save memory
        /// 
        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;
            }
        }

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

            List valuesLeft = new List(_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;
        }

       //************************************************************************
    }
}
0
қосылды