تباديل

للاستخدامات الأخرى، انظر تباديل (توضيح).

Each of the six rows is a different permutation of three distinct balls

التراتيب Permutation هي عدد التشكيلات الممكنة لمجموعة جزئية من العناصر منتقاة من مجموعة كلية من العناصر مع مراعاة لأهمية تسلسل العناصر في تشكيلات المجموعة الجزئية. أوبعبارة أخرى عدد إمكانات ترتيب ر عنصر منتقاة من ن عنصر بشرط الترتيب وعدم تكرار نفس العنصر في التشكيل. رياضيا تحسب التراتيب وفقا للعلاقة التالية: ت(ن، ر)=ن!\(ن-ر)! حيث ن! تعني ن عاملي وتعهد حسب العلاقة التالية: ن!=ن×(ن-1)×(ن-2)×(ن-3)×(ن-4)×.......×3×2×1 وت(ن، ر) عدد التراتيب، أي مجموع الكيفيات التي يمكن حتى ننتقي بها أفراد المجموعة مع مراعاة الترتيب. ن: عدد أفراد المجموعة التي يراد ترتيبها. ر: يرمز إلى كيفية اخذ أفراد المجموعة.

التباديل

إذا كان عدد عناصر المجموعة الجزئية(r) مساويا لعدد عناصر المجموعة الكلية(ن)تدعى التراتيب في هذة الحالة بالتباديل وتعهد رياضيا كما يلي: ل(ن)=ت(ن، ن)= ن!/0!= ن!=ن×(ن-1)×(ن-2)×(ن-3)×(ن-4)×.......×3×2×1 حيث من المعلوم ان 0!=1

مثال

يراد سحب كرتين على التتالي من صندوق اسود يحوي اربع كرات ملونة سوداء وزرقاء وحمراءوصفراء. المطلوب حساب عدد الاحتمالات الممكنة لنتيجة السحب.

الحل

كون السحب يتم على التتالي فان هناك اهمية للترتيب لانه إذا كانت الكرة الأولى على سبيل المثال سوداء والثانية حمراء هذه النتيجة تختلف عن الحالة التيقد يكون فيها الكرة الأولى حمراء والثانية سوداء بتطبيق القانون نحصل على عدد الاحتمالات الممكنة

ت(2,4)=4!\(4-2)!=4×3×2×1 /2×1 = 12 احتمال ممكن وهي بالتفصيل كالتالي: (سوداء، حمراء) (حمراء، سوداء) (زرقاء، سوداء) (صفراء، سوداء) (سوداء، زرقاء) (حمراء، زرقاء) (زرقاء، حمراء) (صفراء، حمراء) (سوداء، صفراء) (حمراء، صفراء) (زرقاء، صفراء) (صفراء، زرقاء)

التباديل في الحوسبة

تباديل الترقيم

مخطط روث لـ ${\displaystyle \sigma =(6,3,8,1,4,9,7,2,5)$
_i ＼ ^σ_i	1	2	3	4	5	6	7	8	9	Lehmer code
1	×	×	×	×	×	•				d₉ = 5
2	×	×	•							d₈ = 2
3	×	×		×	×		×	•		d₇ = 5
4	•									d₆ = 0
5		×		•						d₅ = 1
6		×			×		×		•	d₄ = 3
7		×			×		•			d₃ = 2
8		•								d₂ = 0
9					•					d₁ = 0
inversion table	3	6	1	2	4	0	2	0	0

for i from n downto 2

do d_i ← random element of { 0, ..., i − 1
swap a[d_i] and a[i − 1]

التباديل المياندرية

Meandric systems give rise to , a special subset of alternate permutations. An alternate permutation of the set {1, 2, …, 2n is a cyclic permutation (with no fixed points) such that the digits in the cyclic notation form alternate between odd and even integers. Meandric permutations are useful in the analysis of RNA secondary structure. Not all alternate permutations are meandric. A modification of Heap's algorithm has been used to generate all alternate permutations of order n (that is, of length 2n) without generating all (2n)! permutations.^[] Generation of these alternate permutations is needed before they are analyzed to determine if they are meandric or not.

The algorithm is recursive. The following table exhibits a step in the procedure. In the previous step, all alternate permutations of lengthخمسة have been generated. Three copies of each of these have a "6" added to the right end, and then a different transposition involving this last entry and a previous entry in an even position is applied (including the identity; i.e., no transposition).

Previous sets	Transposition of digits	Alternate permutations
1-2-3-4-5-6		1-2-3-4-5-6
	4, 6	1-2-3-6-5-4
	2, 6	1-6-3-4-5-2
1-2-5-4-3-6		1-2-5-4-3-6
	4, 6	1-2-5-6-3-4
	2, 6	1-6-5-4-3-2
1-4-3-2-5-6		1-4-3-2-5-6
	2, 6	1-4-3-6-5-2
	4, 6	1-6-3-2-5-4
1-4-5-2-3-6		1-4-5-2-3-6
	2, 6	1-4-5-6-3-2
	4, 6	1-6-5-2-3-4

الاستخدامات

Permutations are used in the interleaver component of the error detection and correction algorithms, such as turbo codes, for example 3GPP Long Term Evolution mobile telecommunication standard uses these ideas (see 3GPP technical specification 36.212 ). Such applications raise the question of fast generation of permutations satisfying certain desirable properties. One of the methods is based on the permutation polynomials. Also as a base for optimal hashing in Unique Permutation Hashing.

انظر أيضاً

Alternating permutation
Binomial coefficient
Combination
Combinatorics
Convolution
Cyclic order
Cyclic permutation
Even and odd permutations
Factorial number system
Josephus permutation
Levi-Civita symbol
List of permutation topics
Major index
Necklace (combinatorics)
Permutation group
Permutation pattern
Permutation polynomial
Permutation representation (symmetric group)
Probability
Random permutation
Rencontres numbers
Sorting network
Substitution cipher
Superpattern
Symmetric group
Twelvefold way
Weak order of permutations

الهامش

^ Alexiou, A.; Psiha, M.; Vlamos, P. (2011). "Combinatorial permutation based algorithm for representation of closed RNA secondary structures". Bioinformation. 7 (2): 91–95. doi:10.6026/97320630007091. PMC 3174042. PMID 21938211.
^ 3GPP TS 36.212
^ Dolev, Shlomi; Lahiani, Limor; Haviv, Yinnon (2013). "Unique permutation hashing". Theoretical Computer Science. 475: 59–65. doi:10.1016/j.tcs.2012.12.047.