- 论坛徽章:
- 0
|
“十进制数 <--> 变进制数 <--> 排列”的之间转换实现
在“十进制数 <--> 变进制数 <--> 排列”的转换中，
（1）从十进制数到变进制数的转换方法与p进制数之间的转换类似，但区别是被除数和模数是依次是2,3,4,...n，而不是固定的p
（2）从变进制数到排列的转换算法如下：
使用一个有序的（升序）元素集合作为初始待排子集，然后按照如下过程处理：
从变进制数的高位向低位扫描，对于变进制数的每一位ai，
从当前待排子集中选出第ai+1大元素E，并把它与当前待排子集中它后面的子序列进行交换，然后从当前待排子集中去掉元素E
重复以上过程，直到所有变进制数的位扫描完毕，此时当前待排子集将刚好剩下一个元素，得到与变进制数对应的排列
“十进制数 <--> 变进制数 <--> 排列”之间的转换代码如下：
- #include <iostream>
- #include <iterator>
- #include <vector>
- #include <algorithm>
- #include <cassert>
- using namespace std;
- // 把十进制数转换为变进制数，并返回变进制数的位数
- // 变进制数varNumber[0]对应着变进制数的最低位
- int DecimalToVariableRadix(size_t decimalNumber, vector<int> &varNumber)
- {
- varNumber.clear();
- int carry = 2;
- while (decimalNumber > 0) {
- varNumber.push_back(decimalNumber % carry);
- decimalNumber /= carry;
- ++carry;
- }
- if (varNumber.empty())
- varNumber.push_back(0);
- return varNumber.size();
- }
- // 把十进制数转换为指定位数的变进制数（高位填充0），并返回变进制数的实际有效位数
- // 如果产生的变进制数的位数比指定的位数要多，则指定位数不起作用
- // 变进制数varNumber[0]对应着变进制数的最低位
- int DecimalToVariableRadix(size_t decimalNumber, vector<int> &varNumber, int num)
- {
- varNumber.clear();
- int carry = 2;
- while (decimalNumber > 0) {
- varNumber.push_back(decimalNumber % carry);
- decimalNumber /= carry;
- ++carry;
- }
- int size = varNumber.size();
- if (size < num)
- varNumber.insert(varNumber.end(), num - size, 0);
- return size;
- }
- // 把变进制数转换为十进制数
- // 变进制数varNumber[0]对应着变进制数的最低位
- size_t VariableRadixToDecimal(const int varNumber[], int num)
- {
- size_t factor = 1;
- size_t result = 0;
-
- for (int i = 0; i < num; ++i) {
- result += varNumber[i] * factor;
- factor *= i + 2;
- }
- return result;
- }
- // 把排列转换为变进制数，变进制数的高位可能会出现多个0
- // 变进制数varNumber[0]对应着变进制数的最低位
- template <typename ElemType>
- void PermutationToVariableRadix(const ElemType permutation[], int num, vector<int> &varNumber)
- {
- for (int i = 1; i < num; ++i) {
- int count = 0;
- for (int k = 0; k < i; ++k) {
- if (permutation[k] > permutation[i])
- ++count;
- }
- varNumber.push_back(count);
- }
- }
- // 把变进制数转换为排列，要求传入的排列元素集合是有序的（升序）
- // 并且要求变进制数的位数（包括高位的0）刚好比排列元素少一
- // 变进制数varNumber[0]对应着变进制数的最低位
- template <typename ElemType>
- void VariableRadixToPermutation(const int varNumber[], int num, ElemType perm[])
- {
- for (int k = num - 1; k >= 0; --k) {
- // 交换当前待排子集中第(varNumber[k] + 1)大元素和它后面的子序列
- int m = k + 1; // 当前待排子集中最后一个元素下标
- int j = m - varNumber[k]; // 当前待排子集中第(varNumber[k] + 1)大元素
- #if 0
- // 实现std::rotate的功能
- ElemType tmp = perm[j];
- for (; j < m; ++j)
- perm[j] = perm[j + 1];
- perm[m] = tmp;
- #else
- rotate(perm + j, perm + j + 1, perm + m + 1);
- #endif
- }
- }
- //////////////////////////////////////////////////////////////////////////////////////
- class AssureException: public std::exception
- {
- };
- #define Assure(os, x) (void)((!!(x)) || (ShowFailedMessage(os, #x, __FILE__, __LINE__), 0))
- inline void ShowFailedMessage(std::ostream &os, const char* expr, const char *file, size_t line)
- {
- os << "Failed: " << expr << ", file \"" << file << "\", line " << line << '\n';
- throw AssureException();
- }
- void ShowUsage1()
- {
- try {
- size_t num = 235;
- vector<int> varNumber;
- DecimalToVariableRadix(num, varNumber);
- cout << "Decimal number: " << num;
- cout << "\nConverted to variable radix number (low -> high): ";
- copy(varNumber.begin(), varNumber.end(), ostream_iterator<int>(cout, " "));
- size_t newNum = VariableRadixToDecimal(&varNumber[0], varNumber.size());
- cout << "\nConverted back to decimal number: " << newNum << '\n';
- Assure(cout, num == newNum);
- cout << endl;
- }
- catch (AssureException) {
- }
- }
- void ShowUsage2()
- {
- try {
- char perm[] = {'d', 'e', 'a', 'b', 'f', 'c', 'g'};
- const int NUM = sizeof(perm) / sizeof(perm[0]);
- vector<int> varNumber;
- PermutationToVariableRadix(perm, NUM, varNumber);
- cout << "Permutation: ";
- copy(perm, perm + NUM, ostream_iterator<char>(cout));
- cout << "\nConverted to variable radix number (low -> high): ";
- copy(varNumber.begin(), varNumber.end(), ostream_iterator<int>(cout, " "));
- char newPerm[NUM] = {'a', 'b', 'c', 'd', 'e', 'f', 'g'};
- VariableRadixToPermutation(&varNumber[0], varNumber.size(), newPerm);
- cout << "\nConverted back to permutation: ";
- copy(newPerm, newPerm + NUM, ostream_iterator<char>(cout));
- cout << '\n';
- Assure(cout, equal(perm, perm + NUM, newPerm));
- cout << endl;
- }
- catch (AssureException) {
- }
- }
- void Test()
- {
- try {
- cout << "testing \"permutation -> variable radix -> decimal -> "
- "variable radix -> permutation\"...";
- const int NUM = 9;
- char perm[NUM] = {'1', '2', '3', '4', '5', '6', '7', '8', '9'};
- do {
- // permutation will be converted to variable radix number
- vector<int> varNumber;
- PermutationToVariableRadix(perm, NUM, varNumber);
- // variable radix number will be converted to decimal number
- size_t decimalNumber = VariableRadixToDecimal(&varNumber[0], varNumber.size());
- // decimal number will be converted back to variable radix number
- vector<int> newVarNumber;
- DecimalToVariableRadix(decimalNumber, newVarNumber, NUM - 1);
- // variable radix number will be converted back to permutation
- char newPerm[NUM] = {'1', '2', '3', '4', '5', '6', '7', '8', '9'};
- VariableRadixToPermutation(&newVarNumber[0], newVarNumber.size(), newPerm);
- Assure(cout, equal(varNumber.begin(), varNumber.end(), newVarNumber.begin()));
- Assure(cout, equal(perm, perm + NUM, newPerm));
- } while (next_permutation(perm, perm + NUM));
- cout << "done. Ok!" << endl;
- }
- catch (AssureException) {
- }
- }
- int main()
- {
- ShowUsage1();
- ShowUsage2();
- Test();
- }
|
|
免费注册
楼主: tyc611
发表于 2008-10-09 12:54
