Binary number & Base N number &Permutation&N queens
3 min readFeb 21, 2020
I’d like to build the connection between Permutation and N queens problem.
Base N number system with N “BITs”. “BITs” here means symbols.
Assume N queens are putted column by column
Base N number with N “BIT” = N queens without any constraints.
Permutation = N queens with row constraints but no diagonal constraints.
N queens = N queens (it has both row and diagonal constraints)
Leet code 46 permutations codes.
Solution 1 naively enumerating
C++
An ugly recursion code
/*
jimmy shen
02/20/2020
A code to implement the naive o(n^n) permutation algorithm.
runtime 232 ms
time complexity O(n^n)
space complexity O(n^n) as we introduce an extra container productions
*/class Solution {
public:
vector<vector<int>> permute(vector<int>& nums) {
// productions may have repeatings. It is supposed to have n^n elements.
vector<vector<int>> productions={{}};
vector<vector<int>> permutations;
// iteratively generate productions.
for (int i=0;i<nums.size();++i){
vector<vector<int>> new_productions;
for(auto &num:nums){
for(auto& prod:productions){
vector<int> new_prod = prod;
new_prod.push_back(num);
new_productions.push_back(new_prod);
}
}
productions = new_productions;
}
// generate the final results by removing results which has repeating.
for(auto&prod:productions){
// compare the size of set s to nums.size(). If s.size()==nums.size(), there is no repeating.
unordered_set<int> s(prod.begin(), prod.end());
if (s.size()==nums.size()){
vector<int> permu(prod.begin(), prod.end());
permutations.push_back(permu);
}
}
return permutations;
}
};
A OK iteration code
/*
jimmy shen
02/20/2020
A code to implement the naive o(n^n) permutation algorithm.
runtime 72 ms
time complexity O(n^n)
space complexity O(n^n) as we introduce an extra container productions
*/class Solution {
public:
vector<vector<int>> permute(vector<int>& nums) {
// productions may have repeatings. It is supposed to have n^n elements.
vector<vector<int>> productions={{}};
vector<vector<int>> permutations;
// iteratively generate productions.
//productions = product(nums, 0);
for (int i=0;i<nums.size();++i){
vector<vector<int>> new_productions;
for(auto &num:nums){
for(auto& prod:productions){
vector<int> new_prod = prod;
new_prod.push_back(num);
new_productions.push_back(new_prod);
}
}
productions = new_productions;
}
// generate the final results by only using valid results. Valid here means no repeating.
for(auto&prod:productions){
// compare the size of set s to nums.size(). If s.size()==nums.size(), there is no repeating.
unordered_set<int> s(prod.begin(), prod.end());
if (s.size()==nums.size()){
vector<int> permu(prod.begin(), prod.end());
permutations.push_back(permu);
}
}
return permutations;
}
};
A better recursion code
/*
jimmy shen
02/20/2020
A code to implement the naive o(n^n) permutation algorithm.
runtime 208 ms
time complexity O(n^n)
space complexity O(n)
*/class Solution {
vector<vector<int>> permutations_;
public:
bool has_repeat(vector<int>&numbers){
unordered_set<int> s(numbers.begin(), numbers.end());
return s.size()!=numbers.size();
}
void permute(vector<int>&nums, vector<int>&this_permu, int low){
const int n = nums.size();
vector<int> temp = this_permu;
// if size of this_permu reach to n and it has no repeating, collect this result.
if(temp.size()==n && !has_repeat(temp)){
permutations_.push_back(temp);
return;
}
for( int j = low; j < n; ++j){
for(auto &num:nums){
temp.push_back(num);
permute(nums, temp, j+1);
temp.pop_back();
}
}
}
vector<vector<int>> permute(vector<int>& nums) {
vector<int> this_permu;
permute(nums, this_permu, 0);
return permutations_;
}
};
A N queens similar approach
/*
jimmy shen
02/20/2020
A code to implement the o(n!) permutation algorithm with earlier pruning. It is similar to the N queens problem. Permutation is like N queens problem without diagonal constraints.
runtime 16 ms
time complexity O(n^n)
space complexity O(n) as we have visited
*/class Solution {
vector<vector<int>> permutations_;
public:
void permute(vector<int>&nums, vector<int>&this_permu, int low, vector<int>&visited){
const int n = nums.size();
vector<int> temp = this_permu;
// if size of this_permu reach to n and it has no repeating, collect this result.
if(temp.size()==n){
permutations_.push_back(temp);
return;
}
for( int j = low; j < n; ++j){
for(int i=0; i<n; ++i){
int num = nums[i];
if(!visited[i]){
visited[i] = true;
temp.push_back(num);
permute(nums, temp, j+1, visited);
temp.pop_back();
visited[i] = false;
}
}
}
}
vector<vector<int>> permute(vector<int>& nums) {
vector<int> this_permu, visited(nums.size());
permute(nums, this_permu, 0, visited);
return permutations_;
}
};
Python
"""
jimmy shen
02/20/2020
A code to implement the naive o(n^n) permutation algorithm.
runtime 72 ms
time complexity O(n^n)
space complexity O(n)
"""class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
return [perm for perm in itertools.product(*[nums]*len(nums)) if len(perm)==len(set(perm))]
Other solutions.
