python 改變詞典順序

Description:

描述：

This is a standard interview problem to find out the power sets in lexicographic order of a given set of numbers using backtracking.

這是一個標準的面試問題，它使用回溯來按給定數字集的字典順序查找能力集。

Problem statement:

問題陳述：

There is a set contains N no. of unsorted characters. You have to find out the power sets in lexicographic order of a given set of numbers and print them.

有一組包含N個編號。 未排序的字符。 您必須按字典順序找出給定數字集的冪集并打印出來。

    Input:
Test case T
//T no. of line with the value of N and corresponding values.
E.g.
2
4
d c b a
2 
f u
1<=T<=100
1<=N<=1000
Output:
Print the power subsets of the set in lexicographic order.

Example

例

    T=2
N=4
d c b a
Output:
a
a b
a b c
a b c d
a b d
a c
a c d
a d
b
b c
b c d
b d
c
c d
d 
N=2 
f u
Output:
f
f u
u

Explanation with example

舉例說明

Let, there is a Set S having N no. of numbers.

令，存在具有N no的集合S。 數字。

    S = {X1, X2, X3, ..., Xn}

The process to print the subsets of the set is a problem of combination and permutation. To get the result we use the backtracking process.

打印集合子集的過程是組合和排列的問題。 為了獲得結果，我們使用了回溯過程。

First, we will have to sort the character and then we will apply our backtracking procedure.

首先，我們必須對字符進行排序，然后再應用回溯過程。

Let, f(i) = function to insert the i^th number into a subset.

設f(i)=將第i ^個數字插入子集的函數。

Here, we take a subset of that set in our consideration and consider two things,

在這里，我們考慮一下該集合的子集，并考慮兩件事，

1. An element is a part of that subset (f(i)).

   元素是該子集( f(i) )的一部分。

2. An element is not a part of that subset (not f(i)).

   元素不是該子集的一部分( 不是f(i) )。

For     N=3
S = {a b c}

Figure 1: Recursion Tree

圖1：遞歸樹

Algorithm:

算法：

Here we use the vector STL to store the subsets.

在這里，我們使用向量STL來存儲子集。

    traverse(arr, n, current_pos,set,subset){
if(Current_pos is greater or equals to the n)Then
return
end if
for i= current_pos to the end of the set
insert the element of arr[i] into subset
insert the subset into the set
traverse(arr,n,i+1,set,subset)
pop the element from subset
end for
}

C++ implementation:

C ++實現：

#include <bits/stdc++.h>
using namespace std;
void traverse(char* arr, int n, int pos, vector<vector<char> >& v, vector<char> vi)
{
//if the current position is greater than or equals to n
if (pos >= n)
return;
for (int i = pos; i < n; i++) {
vi.push_back(arr[i]);
v.push_back(vi);
traverse(arr, n, i + 1, v, vi);
vi.pop_back();
}
}
vector<vector<char> > find_subset(char* arr, int n)
{
vector<vector<char> > v;
vector<char> vi;
int pos = 0;
traverse(arr, n, pos, v, vi);
return v;
}
void print(vector<vector<char> > v)
{
for (int i = 0; i < v.size(); i++) {
for (int j = 0; j < v[i].size(); j++) {
cout << v[i][j] << " ";
}
cout << endl;
}
}
int main()
{
int t;
cout << "Test Case : ";
cin >> t;
while (t--) {
int n;
cout << "Enter the value of n : ";
cin >> n;
char arr[n];
//taking the set elements
cout << "Enter the values : ";
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
//sort the elements
sort(arr, arr + n);
vector<vector<char> > v = find_subset(arr, n);
//print the vector
print(v);
}
return 0;
}

Output

輸出量

Test Case : 2
Enter the value of n : 4
Enter the values : d c b a
a
a b
a b c
a b c d
a b d
a c
a c d
a d
b
b c
b c d
b d
c
c d
d
Enter the value of n : 2
Enter the values : f u
f
f u
u

翻譯自: https://www.includehelp.com/icp/power-set-in-lexicographic-order.aspx

python 改變詞典順序