-
June 7th, 2017, 08:19 AM
#1
c permutation code
Hello, I need to have a code to create permutations giving an array of size number of elements and a range...
something like 4 permutation 2, o 5 permutation 3...
unfortunately this code has to be in c and not c++ so things like next permutation cannot be used...
this is the code I was trying to use but it doesnt do it correctly, can anyone propose a better one or correct this one ?
Code:
void permutationUtil(int arr[], int store[],int index, int range, int start, int end)
{ //store size == range+1 :: end == sizeof(arr)-1
// Since index has ==r, current permutation is
// ready to be printed, print
if (index == range)
{
for (int i = 0; i < range; i++)
{
printf("%d ", store[arr[i]]);
}
printf("\n");
return;
}
// One by one choose all elements (without considering
// the fact whether element is already chosen or not)
// and recur
for (int i = start; i <= end; i++)
{
store[index] = i;
permutationUtil(arr, store, index + 1, range, i, end);
}
return;
}
-
June 7th, 2017, 09:51 PM
#2
Re: c permutation code
The following code would generate whole permutation set with the help of held indices' array, obviously the count of the elements in this set should be N!.
Code:
#include <stdio.h>
bool permutation(int *ar, int n) {
int i = n - 2, j, k;
while (i >= 0 && ar[i] >= ar[i + 1]) --i;
if (i >= 0) {
j = i + 1;
while (ar[i] < ar[j + 1]) ++j;
ar[i] ^= ar[j] ^= ar[i] ^= ar[j];
}
for (j = i + 1, k = n - 1; j < k; ar[j] ^= ar[k] ^= ar[j] ^= ar[k], ++j, --k);
return i >= 0;
}
int main() {
int a[] = { 0, 1, 2, 3, 4 };
int b[] = { 1, 2, 3, 4, 5 };
const int n = sizeof(a) / sizeof(a[0]);
do {
for(int i = 0; i < n; ++i)
printf("%d\ ", b[a[i]]);
printf("%c", '\n');
}
while (permutation(a, n));
return 0;
}
Have a nice day.
-
June 8th, 2017, 02:12 AM
#3
Re: c permutation code
please, note that there's no 'bool' in C, and that the expression ( obfuscation aside ) 'ar[i] ^= ar[j] ^= ar[i] ^= ar[j]' is undefined behaviour because you're reading/modifying the same object twice between two consecutive sequence points... ( this would be true for c++ as well, at least up to c++2003; it's probably valid as for >=c++11, but I should check the wording to be sure ... anyway, there's no point using such experssions unless you're writing in crypto-C )
Last edited by superbonzo; June 8th, 2017 at 02:16 AM.
Reason: typos
-
June 8th, 2017, 02:31 AM
#4
Re: c permutation code
Thanks for valuable comments, superbonzo.
The swap expression can be easily substituted with code which uses a temporary variable or just write it to another way.
-
June 8th, 2017, 04:36 AM
#5
Re: c permutation code
For another take on this, consider
Code:
#include <stdio.h>
#include <stdlib.h>
void perm(const int* const data, int* const column, const int k, const int n, const int r)
{
for (column[k] = -1; ++column[k] < n;)
if (k < r - 1)
perm(data, column, k + 1, n, r);
else {
for (int j = 0; j < r; ++j)
printf("%i ", data[column[j]]);
printf("\n");
}
}
int main()
{
const int data[] = { 11, 12, 13, 14, 15 };
const int n = sizeof(data) / sizeof(data[0]);
int *column = (int*)calloc(n, sizeof(int));
perm(data, column, 0, n, 3);
free (column);
}
Where this will generate and display nP3 permutations from the array data.
Last edited by 2kaud; June 8th, 2017 at 06:06 AM.
All advice is offered in good faith only. All my code is tested (unless stated explicitly otherwise) with the latest version of Microsoft Visual Studio (using the supported features of the latest standard) and is offered as examples only - not as production quality. I cannot offer advice regarding any other c/c++ compiler/IDE or incompatibilities with VS. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/ and can be used without reference or acknowledgement. Also note that I only provide advice and guidance via the forums - and not via private messages!
C++23 Compiler: Microsoft VS2022 (17.6.5)
Posting Permissions
- You may not post new threads
- You may not post replies
- You may not post attachments
- You may not edit your posts
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|