Permutations I I Algorithm
The survey of permutations of finite sets is an important subject in the fields of combinatorics and group theory. In elementary combinatorics, the K-permutations, or partial permutations, are the ordered agreements of K distinct components choose from a set. Stedman widens the consideration of permutations; he goes on to consider the number of permutations of the letters of the alphabet and of horses from a stable of 20.A first case in which apparently unrelated mathematical questions were study with the help of permutations happened around 1770, when Joseph Louis Lagrange, in the survey of polynomial equations, detected that property of the permutations of the beginnings of an equation are associated to the possibility to solve it. Fabian Stedman in 1677 described factorials when explaining the number of permutations of Bell in change ringing. The rule to determine the number of permutations of n objects was known in Indian culture around 1150.
class Solution {
public:
vector<vector<int> > permuteUnique(vector<int> &num) {
vector<vector<int>> result;
sort(num.begin(), num.end());
do {
result.push_back(num);
} while (getNext(num));
return result;
}
bool getNext(vector<int>& num) {
int i = num.size() - 1;
while (i >= 1 && num[i-1] >= num[i]) {
i--;
}
if (i == 0) {
return false;
}
int j = num.size() - 1;
while (j >= i) {
if (num[j] > num[i-1]) {
break;
}
j--;
}
swap(num[i-1], num[j]);
reverse(num.begin() + i, num.end());
return true;
}
};
// recursive solution
class Solution {
public:
void helper(vector<vector<int>>& result, vector<int>& num, int x) {
if (x == num.size()) {
result.push_back(num);
return;
}
helper(result, num, x + 1);
map<int, bool> hash;
hash[num[x]] = true;
for (int i = x + 1; i < num.size(); i++) {
if (hash[num[i]]) {
continue;
}
hash[num[i]] = true;
swap(num[x], num[i]);
helper(result, num, x + 1);
swap(num[x], num[i]);
}
}
vector<vector<int> > permuteUnique(vector<int> &num) {
sort(num.begin(), num.end());
vector<vector<int>> result;
helper(result, num, 0);
return move(result);
}
};
