Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Кездейсоқ пермутациялардың циклдік құрылымы сияқты кездейсоқ пермутациялардың статистикасы алгоритмдерді, әсіресе кездейсоқ пермутацияларға жұмыс істейтін сұрыптау алгоритмдерін талдауда негізгі маңызға ие. Мысалы, біз кездейсоқ пермутация кездейсоқ элементін таңдау үшін quickselect (quicksort туысы) қолданамыз деп болжам жасаймыз. Quickselect массивті пішіндіге сәйкес бөледі. Сондықтан тез таңдаудан кейін пермутация бұзылуы аз болады. Қалған тәртіпсіздіктің мөлшері генерациялау функциялары арқылы талдануы мүмкін. Бұл генерациялау функциялары кездейсоқ пермутация статистикасының генерациялау функцияларына негізделген. Сондықтан бұл генерациялық функцияларды есептеу өте маңызды. Кездейсоқ пермутацияларға арналған мақалада кездейсоқ пермутацияларға кіріспе бар.
The statistics of random permutations, such as the cycle structure of a random permutation are of fundamental importance in the analysis of algorithms, especially of sorting algorithms, which operate on random permutations. Suppose, for example, that we are using quickselect (a cousin of quicksort) to select a random element of a random permutation. Quickselect will perform a partial sort on the array, as it partitions the array according to the pivot. Hence a permutation will be less disordered after quickselect has been performed. The amount of disorder that remains may be analysed with generating functions. These generating functions depend in a fundamental way on the generating functions of random permutation statistics. Hence it is of vital importance to compute these generating functions. The article on random permutations contains an introduction to random permutations.
Бірдей цикл инварианттары
Алдыңғы екі бөлімде ұсынылған пермутациялар түрлері, яғни жұп циклдердің жұп санын қамтитын пермутациялар және квадраттар пермутациялары Сунг пен Чжан зерттеген, жұп цикл инварианттарының мысалдары болып табылады (сыртқы сілтемелерді қараңыз). "Кейбір цикл инварианты" термині тек тиісті комбинаторлық класқа мүшелік ету пермутациядағы пайда болатын қайсыбір циклдердің мөлшері мен санына тәуелсіз екенін білдіреді. Шын мәнінде, біз барлық тақ цикл инварианттарының қарапайым қайталануға бағынатынын дәлелдей аламыз, біз оны шығарамыз. Біріншіден, мына жерде біртүрлі цикл инварианттарының тағы бірнеше мысалы келтірілген.
The types of permutations presented in the preceding two sections, i. e. permutations containing an even number of even cycles and permutations that are squares, are examples of so called odd cycle invariants, studied by Sung and Zhang (see external links). The term odd cycle invariant simply means that membership in the respective combinatorial class is independent of the size and number of odd cycles occurring in the permutation. In fact we can prove that all odd cycle invariants obey a simple recurrence, which we will derive. First, here are some more examples of odd cycle invariants.
Жалпылау
Осындай статистика шекті жиынтықтағы кездейсоқ эндоморфизмдер үшін де қол жетімді.
Similar statistics are available for random endomorphisms on a finite set.