التقليب السريع -> رقم -> خوارزميات رسم الخرائط
https://stackoverflow.com/questions/1506078
-
19-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russianسؤال
لدي عناصر ن. من أجل مثال، دعنا نقول، 7 عناصر، 1234567. أعرف أن هناك 7! = 5040 التباديل ممكن من هذه العناصر 7.
أريد خوارزمية سريعة تضم وظيفتين:
F (رقم) خرائط رقم بين 0 و 5039 إلى التقليب الفريد، و
F '(التقليب) خرائط التقليب مرة أخرى إلى الرقم الذي تم إنشاؤه منه.
لا يهمني المراسلات بين العدد واللقب، حيث يوفر كل التقليب رقم فريد خاص به.
لذلك، على سبيل المثال، قد يكون لدي وظائف أين
f(0) = '1234567'
f'('1234567') = 0
أسرع الخوارزمية التي تتبادر إلى الذهن هي تعداد جميع التباديل وإنشاء جدول بحث في كلا الاتجاهين، بحيث، بمجرد إنشاء الجداول، ستكون F (0) O (1) و F ('1234567) بحث على سلسلة. ومع ذلك، فإن هذه هي الذاكرة الجياع، خاصة عندما تصبح N كبيرة.
هل يمكن لأي شخص يقترح خوارزمية أخرى من شأنها أن تعمل بسرعة ودون عيب الذاكرة؟
المحلول
لوصف اعتبارات Nements N، ترى أنه من أجل الموضع الذي ينتهي به العنصر الأول، لديك إمكانيات N، حتى تتمكن من وصف ذلك برقم بين 0 و N-1. بالنسبة للموضع الذي ينتهي العنصر التالي، لديك إمكانيات N-1 المتبقية، حتى تتمكن من وصف ذلك برقم بين 0 و N-2.
ET Cetera حتى يكون لديك أرقام N.
كمثال ل n = 5، النظر في التقليب الذي يجلب abcde ل caebd.
a, ، العنصر الأول، ينتهي في المركز الثاني، لذلك نحن نعرف مؤشر تكنولوجيا المعلومات 1.bينتهي في المركز الرابع، الذي سيكون مؤشرا 3، لكنه الثالث المتبقي، لذلك نعرفه 2.cينتهي في الوضع الأول المتبقي، وهو دائما 0.dينتهي في آخر موقف المتبقية، والتي (من مواقف اثنين فقط المتبقية) هي 1.eينتهي في الموضع الوحيد المتبقي، مفهرسة في 0.
لذلك لدينا تسلسل المؤشر {1, 2, 0, 1, 0}.
الآن أنت تعرف أنه على سبيل المثال في عدد ثنائي، "XYZ" تعني Z + 2Y + 4X. لعدد عشري،
انها z + 10y + 100x. يضاعف كل رقم من وزن بعض الوزن، ويتم تلخيص النتائج. النمط الواضح في الوزن هو بالطبع أن الوزن هو W = B ^ K، مع B قاعدة الرقم و K فهرس الرقم. (سأحاول دائما حساب الأرقام من اليمين والبدء في الفهرس 0 لأرقام أقصى اليمين. وبالمثل عندما أتحدث عن الرقم الأول "الأول" أقصد أقصى اليمين.)
ال السبب لماذا يتبع الأوزان للأرقام هذا النمط هو أن أعلى رقم يمكن تمثيله بواسطة الأرقام من 0 إلى K يجب أن يكون أقل بالضبط 1 أقل من أقل عدد يمكن أن يمثله فقط باستخدام رقم K + 1 فقط. في ثنائي، يجب أن يكون 0111 أقل من 1000. في العشري، يجب أن يكون 099999 أقل من 100000.
الترميز إلى قاعدة متغيرة
التباعد بين الأرقام اللاحقة يجري بالضبط 1 هو القاعدة المهمة. إدراك ذلك، يمكننا تمثيل تسلسل المؤشر لدينا رقم قاعدة متغير. وبعد القاعدة لكل رقم هي مقدار الاحتمالات المختلفة لهذا الرقم. بالنسبة إلى كل رقم عشري يحتوي كل رقمين على 10 إمكانيات، لنظامنا على أقصى اليمين سيكون لديه احتمال واحد وسوف يكون أقصى اليسار إمكانيات N. ولكن منذ أقصى اليمين (الرقم الأخير في تسلسلنا) هو دائما 0، نتركها. هذا يعني أننا غادرنا مع القواعد 2 إلى ن. بشكل عام، سيكون لدى رقم K'TH FIGIT قاعدة B [K] = K + 2. أعلى قيمة مسموح بها لأرقام K هي H [K] = B [K] - 1 = K + 1.
تتطلب حكمنا حول الأوزان W [K] من الأرقام أن مجموع h [i] * w [i]، حيث أذهب من i = 0 إلى i = k، يساوي 1 * w [k + 1]. ذكرت بشكل متكرر، W [K + 1] = w [k] + h [k] * w [k] = w [k] * (h [k] + 1). يجب أن يكون الوزن الأول W [0] دائما 1. بدءا من هناك، لدينا القيم التالية:
k h[k] w[k]
0 1 1
1 2 2
2 3 6
3 4 24
... ... ...
n-1 n n!
(العلاقة العامة W [K-1] = K! ثبت بسهولة عن طريق الحث.)
سيكون الرقم الذي نحصل عليه من تحويل تسلسلنا هو مجموع S [K] * W [K]، مع K الركض من 0 إلى N-1. هنا S [K] هو عنصر K'TH (أقصى اليمين، بدءا من 0) من التسلسل. كمثال، تأخذ لدينا {1، 2، 0، 1، 0}، مع خطر أقصى اليمين جردت كما هو مذكور من قبل: {1, 2, 0, 1}. وبعد مجموعنا 1 * 1 + 0 * 2 + 2 * 6 + 1 * 24 = 37.
لاحظ أنه إذا أخذنا الحد الأقصى للموضع لكل مؤشر، فلدينا {4 و 3 و 2 و 1 و 0}، وتحول ذلك إلى 119. نظرا لأن الأوزان في ترميزنا قد تم اختياره حتى لا نقوم بالتخطي أي أرقام، جميع الأرقام 0 إلى 119 صالحة. هناك 120 على وجه التحديد من هذه، وهو ن! ل N = 5 في مثالنا، على وجه التحديد عدد التباديلات المختلفة. حتى تتمكن من رؤية أرقامنا المشفرة تحدد تماما جميع التباديلات الممكنة.
فك التشفير من قاعدة متغيرة
فك التشفير مشابه للتحويل إلى ثنائي أو عشري. الخوارزمية الشائعة هي:
int number = 42;
int base = 2;
int[] bits = new int[n];
for (int k = 0; k < bits.Length; k++)
{
bits[k] = number % base;
number = number / base;
}
لعدد الأساس المتغير لدينا:
int n = 5;
int number = 37;
int[] sequence = new int[n - 1];
int base = 2;
for (int k = 0; k < sequence.Length; k++)
{
sequence[k] = number % base;
number = number / base;
base++; // b[k+1] = b[k] + 1
}
هذا فك الترفيز بشكل صحيح لدينا 37 مرة أخرى إلى {1، 2، 0، 1} (sequence سيكون {1, 0, 2, 1} في مثال الرمز هذا، ولكن أيا كان ... طالما كنت مؤشر مناسب). نحتاج فقط إلى إضافة 0 في النهاية الصحيحة (تذكر العنصر الأخير دائما إمكانية واحدة فقط لموقفها الجديد) لاستعادة التسلسل الأصلي لدينا {1، 2، 0، 1، 0}.
بسمية قائمة باستخدام تسلسل الفهرس
يمكنك استخدام الخوارزمية أدناه لمعرفة القائمة وفقا لتسلسل فهرس معين. انها خوارزمية O (N²)، لسوء الحظ.
int n = 5;
int[] sequence = new int[] { 1, 2, 0, 1, 0 };
char[] list = new char[] { 'a', 'b', 'c', 'd', 'e' };
char[] permuted = new char[n];
bool[] set = new bool[n];
for (int i = 0; i < n; i++)
{
int s = sequence[i];
int remainingPosition = 0;
int index;
// Find the s'th position in the permuted list that has not been set yet.
for (index = 0; index < n; index++)
{
if (!set[index])
{
if (remainingPosition == s)
break;
remainingPosition++;
}
}
permuted[index] = list[i];
set[index] = true;
}
التمثيل الشائع للتصارحات
عادة فلن تمثل مبناه بشكل غير أساسي كما فعلنا، ولكن ببساطة من خلال الموقف المطلق لكل عنصر بعد تطبيق التقليب. مثالنا {1، 2، 0، 1، 0} ل abcde ل caebd يمثل عادة {1، 3، 0، 4، 2}. يحدث كل مؤشر من 0 إلى 4 (أو بشكل عام، 0 إلى N-1) بالضبط مرة واحدة في هذا التمثيل.
تطبيق التقليب في هذا النموذج سهل:
int[] permutation = new int[] { 1, 3, 0, 4, 2 };
char[] list = new char[] { 'a', 'b', 'c', 'd', 'e' };
char[] permuted = new char[n];
for (int i = 0; i < n; i++)
{
permuted[permutation[i]] = list[i];
}
إنهاء إنه مشابه جدا:
for (int i = 0; i < n; i++)
{
list[i] = permuted[permutation[i]];
}
تحويل من تمثيلنا إلى التمثيل الشائع
لاحظ أنه إذا أخذنا خوارزميةنا لمعرفة قائمة باستخدام تسلسل الفهرس لدينا، وتطبيقه على التقليب الهوية {0، 1، 2، ...، N-1}، نحصل على معكوس التقليب، ممثلة في الشكل المشترك. في{2, 0, 4, 1, 3} في مثالنا).
للحصول على التوثيق غير المقلوب، نطبق خوارزمية التقليب التي أظهرت للتو:
int[] identity = new int[] { 0, 1, 2, 3, 4 };
int[] inverted = { 2, 0, 4, 1, 3 };
int[] normal = new int[n];
for (int i = 0; i < n; i++)
{
normal[identity[i]] = list[i];
}
أو يمكنك فقط تطبيق التقليب مباشرة، باستخدام خوارزمية التبول العكسية:
char[] list = new char[] { 'a', 'b', 'c', 'd', 'e' };
char[] permuted = new char[n];
int[] inverted = { 2, 0, 4, 1, 3 };
for (int i = 0; i < n; i++)
{
permuted[i] = list[inverted[i]];
}
لاحظ أن جميع خوارزميات التعامل مع التباديلات في النموذج المشترك هي O (n)، أثناء تطبيق التقليب في النموذج الخاص بنا هو O (N²). إذا كنت بحاجة إلى تطبيق التقليب عدة مرات، أولا تحويله إلى التمثيل الشائع.
نصائح أخرى
لقد وجدت خوارزمية O (ن)، إليك شرح قصير http://antoinecomeau.blogspot.ca 2012/07/mapping-between-permutations-and.html.
public static int[] perm(int n, int k)
{
int i, ind, m=k;
int[] permuted = new int[n];
int[] elems = new int[n];
for(i=0;i<n;i++) elems[i]=i;
for(i=0;i<n;i++)
{
ind=m%(n-i);
m=m/(n-i);
permuted[i]=elems[ind];
elems[ind]=elems[n-i-1];
}
return permuted;
}
public static int inv(int[] perm)
{
int i, k=0, m=1;
int n=perm.length;
int[] pos = new int[n];
int[] elems = new int[n];
for(i=0;i<n;i++) {pos[i]=i; elems[i]=i;}
for(i=0;i<n-1;i++)
{
k+=m*pos[perm[i]];
m=m*(n-i);
pos[elems[n-i-1]]=pos[perm[i]];
elems[pos[perm[i]]]=elems[n-i-1];
}
return k;
}
يمكن إحضار التعقيد إلى N * Log (n)، انظر القسم 10.1.1 ("رمز Lehmer (جدول الانعكاس)"، P.232FF) من FXTBook: http://www.jjj.de/fxt/#fxtbook.تخطي إلى القسم 10.1.1.1 ("حساب مع صفائف كبيرة" P.235) للطريقة السريعة. رمز (GPLED، C ++) هو على نفس صفحة الويب.
يمكن أن يكون كل عنصر في واحدة من سبعة مواقع. لوصف موقف عنصر واحد، ستحتاج إلى ثلاثة بت. هذا يعني أنه يمكنك تخزين موضع جميع العناصر في قيمة 32 بت. هذا بعيد عن أن تكون فعالة، لأن هذا التمثيل سيسمح حتى أن تكون جميع العناصر في نفس الموقف، لكنني أعتقد أن اخفاء بعض الشيء يجب أن يكون بسرعة معقولة.
ومع ذلك، مع أكثر من 8 مواقف ستحتاج إلى شيء أكثر أنيقا.
يحدث هذا أن تكون وظيفة مدمجة في ج:
A. 1 2 3 4 5 6 7
0
0 A. 1 2 3 4 5 6 7
1 2 3 4 5 6 7
?!7
5011
5011 A. 1 2 3 4 5 6 7
7 6 4 5 1 3 2
A. 7 6 4 5 1 3 2
5011
تم حل المشكلة. ومع ذلك، لست متأكدا من أنك لا تزال بحاجة إلى الحل بعد هذه السنوات. LOL، أنا فقط انضم إلى هذا الموقع، هكذا ... تحقق من فئة التقليب جافا الخاص بي. يمكنك إنشاء مؤشر للحصول على التقليب الرمز، أو إعطاء رمز رمزا ثم احصل على الفهرس.
ها هي صفي الصفي
/**
****************************************************************************************************************
* Copyright 2015 Fred Pang fred@pnode.com
****************************************************************************************************************
* A complete list of Permutation base on an index.
* Algorithm is invented and implemented by Fred Pang fred@pnode.com
* Created by Fred Pang on 18/11/2015.
****************************************************************************************************************
* LOL this is my first Java project. Therefore, my code is very much like C/C++. The coding itself is not
* very professional. but...
*
* This Permutation Class can be use to generate a complete list of all different permutation of a set of symbols.
* nPr will be n!/(n-r)!
* the user can input n = the number of items,
* r = the number of slots for the items,
* provided n >= r
* and a string of single character symbols
*
* the program will generate all possible permutation for the condition.
*
* Say if n = 5, r = 3, and the string is "12345", it will generate sll 60 different permutation of the set
* of 3 character strings.
*
* The algorithm I used is base on a bin slot.
* Just like a human or simply myself to generate a permutation.
*
* if there are 5 symbols to chose from, I'll have 5 bin slot to indicate which symbol is taken.
*
* Note that, once the Permutation object is initialized, or after the constructor is called, the permutation
* table and all entries are defined, including an index.
*
* eg. if pass in value is 5 chose 3, and say the symbol string is "12345"
* then all permutation table is logically defined (not physically to save memory).
* It will be a table as follows
* index output
* 0 123
* 1 124
* 2 125
* 3 132
* 4 134
* 5 135
* 6 143
* 7 145
* : :
* 58 542
* 59 543
*
* all you need to do is call the "String PermGetString(int iIndex)" or the "int[] PermGetIntArray(int iIndex)"
* function or method with an increasing iIndex, starting from 0 to getiMaxIndex() - 1. It will return the string
* or the integer array corresponding to the index.
*
* Also notice that in the input string is "12345" of position 01234, and the output is always in accenting order
* this is how the permutation is generated.
*
* ***************************************************************************************************************
* ==== W a r n i n g ====
* ***************************************************************************************************************
*
* There is very limited error checking in this class
*
* Especially the int PermGetIndex(int[] iInputArray) method
* if the input integer array contains invalid index, it WILL crash the system
*
* the other is the string of symbol pass in when the object is created, not sure what will happen if the
* string is invalid.
* ***************************************************************************************************************
*
*/
public class Permutation
{
private boolean bGoodToGo = false; // object status
private boolean bNoSymbol = true;
private BinSlot slot; // a bin slot of size n (input)
private int nTotal; // n number for permutation
private int rChose; // r position to chose
private String sSymbol; // character string for symbol of each choice
private String sOutStr;
private int iMaxIndex; // maximum index allowed in the Get index function
private int[] iOutPosition; // output array
private int[] iDivisorArray; // array to do calculation
public Permutation(int inCount, int irCount, String symbol)
{
if (inCount >= irCount)
{
// save all input values passed in
this.nTotal = inCount;
this.rChose = irCount;
this.sSymbol = symbol;
// some error checking
if (inCount < irCount || irCount <= 0)
return; // do nothing will not set the bGoodToGo flag
if (this.sSymbol.length() >= inCount)
{
bNoSymbol = false;
}
// allocate output storage
this.iOutPosition = new int[this.rChose];
// initialize the bin slot with the right size
this.slot = new BinSlot(this.nTotal);
// allocate and initialize divid array
this.iDivisorArray = new int[this.rChose];
// calculate default values base on n & r
this.iMaxIndex = CalPremFormula(this.nTotal, this.rChose);
int i;
int j = this.nTotal - 1;
int k = this.rChose - 1;
for (i = 0; i < this.rChose; i++)
{
this.iDivisorArray[i] = CalPremFormula(j--, k--);
}
bGoodToGo = true; // we are ready to go
}
}
public String PermGetString(int iIndex)
{
if (!this.bGoodToGo) return "Error: Object not initialized Correctly";
if (this.bNoSymbol) return "Error: Invalid symbol string";
if (!this.PermEvaluate(iIndex)) return "Invalid Index";
sOutStr = "";
// convert string back to String output
for (int i = 0; i < this.rChose; i++)
{
String sTempStr = this.sSymbol.substring(this.iOutPosition[i], iOutPosition[i] + 1);
this.sOutStr = this.sOutStr.concat(sTempStr);
}
return this.sOutStr;
}
public int[] PermGetIntArray(int iIndex)
{
if (!this.bGoodToGo) return null;
if (!this.PermEvaluate(iIndex)) return null ;
return this.iOutPosition;
}
// given an int array, and get the index back.
//
// ====== W A R N I N G ======
//
// there is no error check in the array that pass in
// if any invalid value in the input array, it can cause system crash or other unexpected result
//
// function pass in an int array generated by the PermGetIntArray() method
// then return the index value.
//
// this is the reverse of the PermGetIntArray()
//
public int PermGetIndex(int[] iInputArray)
{
if (!this.bGoodToGo) return -1;
return PermDoReverse(iInputArray);
}
public int getiMaxIndex() {
return iMaxIndex;
}
// function to evaluate nPr = n!/(n-r)!
public int CalPremFormula(int n, int r)
{
int j = n;
int k = 1;
for (int i = 0; i < r; i++, j--)
{
k *= j;
}
return k;
}
// PermEvaluate function (method) base on an index input, evaluate the correspond permuted symbol location
// then output it to the iOutPosition array.
//
// In the iOutPosition[], each array element corresponding to the symbol location in the input string symbol.
// from location 0 to length of string - 1.
private boolean PermEvaluate(int iIndex)
{
int iCurrentIndex;
int iCurrentRemainder;
int iCurrentValue = iIndex;
int iCurrentOutSlot;
int iLoopCount;
if (iIndex >= iMaxIndex)
return false;
this.slot.binReset(); // clear bin content
iLoopCount = 0;
do {
// evaluate the table position
iCurrentIndex = iCurrentValue / this.iDivisorArray[iLoopCount];
iCurrentRemainder = iCurrentValue % this.iDivisorArray[iLoopCount];
iCurrentOutSlot = this.slot.FindFreeBin(iCurrentIndex); // find an available slot
if (iCurrentOutSlot >= 0)
this.iOutPosition[iLoopCount] = iCurrentOutSlot;
else return false; // fail to find a slot, quit now
this.slot.setStatus(iCurrentOutSlot); // set the slot to be taken
iCurrentValue = iCurrentRemainder; // set new value for current value.
iLoopCount++; // increase counter
} while (iLoopCount < this.rChose);
// the output is ready in iOutPosition[]
return true;
}
//
// this function is doing the reverse of the permutation
// the input is a permutation and will find the correspond index value for that entry
// which is doing the opposit of the PermEvaluate() method
//
private int PermDoReverse(int[] iInputArray)
{
int iReturnValue = 0;
int iLoopIndex;
int iCurrentValue;
int iBinLocation;
this.slot.binReset(); // clear bin content
for (iLoopIndex = 0; iLoopIndex < this.rChose; iLoopIndex++)
{
iCurrentValue = iInputArray[iLoopIndex];
iBinLocation = this.slot.BinCountFree(iCurrentValue);
this.slot.setStatus(iCurrentValue); // set the slot to be taken
iReturnValue = iReturnValue + iBinLocation * this.iDivisorArray[iLoopIndex];
}
return iReturnValue;
}
/*******************************************************************************************************************
*******************************************************************************************************************
* Created by Fred on 18/11/2015. fred@pnode.com
*
* *****************************************************************************************************************
*/
private static class BinSlot
{
private int iBinSize; // size of array
private short[] eStatus; // the status array must have length iBinSize
private BinSlot(int iBinSize)
{
this.iBinSize = iBinSize; // save bin size
this.eStatus = new short[iBinSize]; // llocate status array
}
// reset the bin content. no symbol is in use
private void binReset()
{
// reset the bin's content
for (int i = 0; i < this.iBinSize; i++) this.eStatus[i] = 0;
}
// set the bin position as taken or the number is already used, cannot be use again.
private void setStatus(int iIndex) { this.eStatus[iIndex]= 1; }
//
// to search for the iIndex th unused symbol
// this is important to search through the iindex th symbol
// because this is how the table is setup. (or the remainder means)
// note: iIndex is the remainder of the calculation
//
// for example:
// in a 5 choose 3 permutation symbols "12345",
// the index 7 item (count starting from 0) element is "1 4 3"
// then comes the index 8, 8/12 result 0 -> 0th symbol in symbol string = '1'
// remainder 8. then 8/3 = 2, now we need to scan the Bin and skip 2 unused bins
// current the bin looks 0 1 2 3 4
// x o o o o x -> in use; o -> free only 0 is being used
// s s ^ skipped 2 bins (bin 1 and 2), we get to bin 3
// and bin 3 is the bin needed. Thus symbol "4" is pick
// in 8/3, there is a remainder 2 comes in this function as 2/1 = 2, now we have to pick the empty slot
// for the new 2.
// the bin now looks 0 1 2 3 4
// x 0 0 x 0 as bin 3 was used by the last value
// s s ^ we skip 2 free bins and the next free bin is bin 4
// therefor the symbol "5" at the symbol array is pick.
//
// Thus, for index 8 "1 4 5" is the symbols.
//
//
private int FindFreeBin(int iIndex)
{
int j = iIndex;
if (j < 0 || j > this.iBinSize) return -1; // invalid index
for (int i = 0; i < this.iBinSize; i++)
{
if (this.eStatus[i] == 0) // is it used
{
// found an empty slot
if (j == 0) // this is a free one we want?
return i; // yes, found and return it.
else // we have to skip this one
j--; // else, keep looking and count the skipped one
}
}
assert(true); // something is wrong
return -1; // fail to find the bin we wanted
}
//
// this function is to help the PermDoReverse() to find out what is the corresponding
// value during should be added to the index value.
//
// it is doing the opposite of int FindFreeBin(int iIndex) method. You need to know how this
// FindFreeBin() works before looking into this function.
//
private int BinCountFree(int iIndex)
{
int iRetVal = 0;
for (int i = iIndex; i > 0; i--)
{
if (this.eStatus[i-1] == 0) // it is free
{
iRetVal++;
}
}
return iRetVal;
}
}
}
// End of file - Permutation.java
وهنا صفي الرئيسي لإظهار كيفية استخدام الفصل.
/*
* copyright 2015 Fred Pang
*
* This is the main test program for testing the Permutation Class I created.
* It can be use to demonstrate how to use the Permutation Class and its methods to generate a complete
* list of a permutation. It also support function to get back the index value as pass in a permutation.
*
* As you can see my Java is not very good. :)
* This is my 1st Java project I created. As I am a C/C++ programmer for years.
*
* I still have problem with the Scanner class and the System class.
* Note that there is only very limited error checking
*
*
*/
import java.util.Scanner;
public class Main
{
private static Scanner scanner = new Scanner(System.in);
public static void main(String[] args)
{
Permutation perm; // declear the object
String sOutString = "";
int nCount;
int rCount;
int iMaxIndex;
// Get user input
System.out.println("Enter n: ");
nCount = scanner.nextInt();
System.out.println("Enter r: ");
rCount = scanner.nextInt();
System.out.println("Enter Symbol: ");
sOutString = scanner.next();
if (sOutString.length() < rCount)
{
System.out.println("String too short, default to numbers");
sOutString = "";
}
// create object with user requirement
perm = new Permutation(nCount, rCount, sOutString);
// and print the maximum count
iMaxIndex = perm.getiMaxIndex();
System.out.println("Max count is:" + iMaxIndex);
if (!sOutString.isEmpty())
{
for (int i = 0; i < iMaxIndex; i++)
{ // print out the return permutation symbol string
System.out.println(i + " " + perm.PermGetString(i));
}
}
else
{
for (int i = 0; i < iMaxIndex; i++)
{
System.out.print(i + " ->");
// Get the permutation array
int[] iTemp = perm.PermGetIntArray(i);
// print out the permutation
for (int j = 0; j < rCount; j++)
{
System.out.print(' ');
System.out.print(iTemp[j]);
}
// to verify my PermGetIndex() works. :)
if (perm.PermGetIndex(iTemp)== i)
{
System.out.println(" .");
}
else
{ // oops something is wrong :(
System.out.println(" ***************** F A I L E D *************************");
assert(true);
break;
}
}
}
}
}
//
// End of file - Main.java
استمتع. :)
يمكنك تشفير التباديل باستخدام خوارزمية متكررة. إذا كان التقليب N (بعض طلب الأرقام {0،، n-1}) من النموذج {x، ...} ثم ترميزه ك X + N * ترميز (N-1) -التفائز الممثلة ب "..." على الأرقام {0، n-1} - {x}. يبدو وكأنه الفم، إليك بعض الكود:
// perm[0]..perm[n-1] must contain the numbers in {0,..,n-1} in any order.
int permToNumber(int *perm, int n) {
// base case
if (n == 1) return 0;
// fix up perm[1]..perm[n-1] to be a permutation on {0,..,n-2}.
for (int i = 1; i < n; i++) {
if (perm[i] > perm[0]) perm[i]--;
}
// recursively compute
return perm[0] + n * permToNumber(perm + 1, n - 1);
}
// number must be >=0, < n!
void numberToPerm(int number, int *perm, int n) {
if (n == 1) {
perm[0] = 0;
return;
}
perm[0] = number % n;
numberToPerm(number / n, perm + 1, n - 1);
// fix up perm[1] .. perm[n-1]
for (int i = 1; i < n; i++) {
if (perm[i] >= perm[0]) perm[i]++;
}
}
هذه الخوارزمية هي O (n ^ 2). نقاط المكافأة إذا كان لدى أي شخص خوارزمية O (n).
يا له من سؤال مثير للاهتمام!
إذا كانت جميع العناصر الخاصة بك هي أرقام، فقد ترغب في التفكير في تحويلها عن الأرقام الفعلية. ثم ستكون قادرا على فرز جميع التباديل عن طريق وضعها في ترتيب، ووضعها في صفيف. بعد ذلك، ستكون مفتوحة لأي من خوارزميات البحث المختلفة هناك.
كنت متسرع في إجابتي السابقة (المحذوفة)، لدي الإجابة الفعلية رغم ذلك. يتم توفيره من قبل مفهوم مماثل، عكسي, وترتبط بالصرافيات (إجابتي المتعلقة بالمجموعات، أعتذر عن هذا الارتباك). أنا أكره فقط نشر روابط ويكيبيديا، لكني تطل أنا فعلت منذ لحظة من غير مؤهل لسبب ما. لذلك، يمكنني التوسع في وقت لاحق إذا طلب ذلك.
هناك كتاب مكتوب حول هذا الموضوع. آسف، لكنني لا أتذكر اسمه (سوف تجد ذلك تماما من ويكيبيديا). ولكن على أي حال، كتبت تطبيق Python لهذا نظام التعداد: http://kks.cabal.fi/kombinaattori.البعض منها باللغة الفنلندية، ولكن فقط نسخ الشفرة ومتغيرات الاسم ...
يسأل مسألة ذات صلة يحتاج إلى التقليب العكسي، وهو التقليب الذي سيستعيد موعظا مسحوبة إلى الترتيب الأصلي عندما يعرف صفيف التقليب فقط. هنا هو رمز O (N) (في PHP):
// Compute the inverse of a permutation
function GetInvPerm($Perm)
{
$n=count($Perm);
$InvPerm=[];
for ($i=0; $i<$n; ++$i)
$InvPerm[$Perm[$i]]=$i;
return $InvPerm;
} // GetInvPerm
ديفيد سبككز برينجت برامج
كان لدي هذا السؤال الدقيق وأعتقد أنني سوف أقدم حل بيثون الخاص بي. انها o (n ^ 2).
import copy
def permute(string, num):
''' generates a permutation '''
def build_s(factoradic): # Build string from factoradic in list form
string0 = copy.copy(string)
n = []
for i in range(len(factoradic)):
n.append(string0[factoradic[i]])
del string0[factoradic[i]]
return n
f = len(string)
factoradic = []
while(f != 0): # Generate factoradic number list
factoradic.append(num % f)
num = (num - factoradic[-1])//f
f -= 1
return build_s(factoradic)
s = set()
# Print 120 permutations of this string
for i in range(120):
m = permute(list('abcde'), i)
s.add(''.join(m))
print(len(s)) # Check that we have 120 unique permutations
انها جميلة مستقيم إلى الأمام؛ بعد توليد تمثيل العدد من العدد، أنا فقط اختر وأزل الأحرف من السلسلة. حذف من السلسلة هو سبب هذا الحل O (n ^ 2).
حل أنطوان أفضل للأداء.
