تباديل

(تم التحويل من تراتيب)
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 احتمال ممكن وهي بالتفصيل كالتالي: (سوداء، حمراء) (حمراء، سوداء) (زرقاء، سوداء) (صفراء، سوداء) (سوداء، زرقاء) (حمراء، زرقاء) (زرقاء، حمراء) (صفراء، حمراء) (سوداء، صفراء) (حمراء، صفراء) (زرقاء، صفراء) (صفراء، زرقاء)

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

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

مخطط روث لـ
i  \ σi 1 2 3 4 5 6 7 8 9 Lehmer code
1 × × × × × d9 = 5
2 × × d8 = 2
3 × × × × × d7 = 5
4 d6 = 0
5 × d5 = 1
6 × × × d4 = 3
7 × × d3 = 2
8 d2 = 0
9 d1 = 0
inversion table 3 6 1 2 4 0 2 0 0


for i from n downto 2
do   di ← random element of { 0, ..., i − 1 }
swap a[di] and a[i − 1]


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

Meandric systems give rise to meandric permutations, 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.[1][مصدر غير موثوق به؟] 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 5 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 [2]). 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.[3]

انظر أيضاً

الهامش


  1. ^ 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.
  2. ^ 3GPP TS 36.212
  3. ^ Dolev, Shlomi; Lahiani, Limor; Haviv, Yinnon (2013). "Unique permutation hashing". Theoretical Computer Science. 475: 59–65. doi:10.1016/j.tcs.2012.12.047.