i’ve just realize that the for loop is also not parallelizable because of the dependecies of the previously swap comming trough i and idx_SUBJECT CLOSED
hello
I am parallelizing a permute algorithm.
Usually permute are recursivelly, iterativelly using “while” loops, or other C++ features which are more or less paralelizable.
the follow algorithm is good from this point of view
But I am trying to reduce the workload - without duplicates.
Please help me to find a good filter for duplicates
The commented code bellow is showing all permutation “with duplicates”. Uncommented it for “without duplicates”.
for example
permutation of 5 numbers = 5! = 120 with repetition means, doesn’t meter the value of them
count permutation 01 - 4 1 0 0 0
count permutation 49 - 4 1 0 0 0 (0 from pos 2 was swap with 0 from pos 3)
count permutation 87 - 4 1 0 0 0 (0 from pos 3 was swap with 0 from pos 4)
permutation of 5 number without duplicates where 3 are “0” takes in account the value of them and is not counting as a permutation, so in the example permutation 49 and 87 will not be shown
it will count only 20 (not doubled) permutations_
#include <cstdio>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <vector>
using namespace std;
int oCr = 5;
void prt(int sir[]) {
for(int i=0; i < oCr; i++)
printf("%d ", sir[i]);
}
int main(void) {
int sir[oCr] = {4, 1, 0, 0, 0};
//int w[oCr][oCr][oCr][oCr] = { };
int idx[oCr] = { };
{ // area to print first permutation
prt(sir);
printf("\n");
}
for (int i = 1; i < oCr;) {
if (idx[i] < i) {
int j = i % 2 * idx[i];
int tmp = sir[j]; //swap
sir[j] = sir[i];
sir[i] = tmp;
{ // area to print all other permutations
//if ((w[j][i][sir[j]][sir[i]] == 0) && (sir[i] != sir[j])) {
//printf("%d", j);
//printf("%d ", i);
//printf("%d", sir[i]);
//printf("%d ", sir[j]);
//printf("%d ", w[j][i][sir[i]][sir[j]]);
prt(sir);
printf("\n");
//}
}
//w[j][i][sir[i]][sir[j]] = 1; // control_array takes value 1
idx[i]++;
i = 1;
}
else {
idx[i++] = 0;
}
}
return 0;
}
S