dcsimg
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 5 of 5

Thread: c permutation code

  1. #1
    Join Date
    Jul 2013
    Posts
    161

    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;
    }

  2. #2
    Join Date
    Jun 2003
    Location
    Armenia, Yerevan
    Posts
    720

    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.
    Popular opinion is the greatest lie in the world.

  3. #3
    Join Date
    Oct 2008
    Posts
    1,456

    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

  4. #4
    Join Date
    Jun 2003
    Location
    Armenia, Yerevan
    Posts
    720

    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.
    Popular opinion is the greatest lie in the world.

  5. #5
    2kaud's Avatar
    2kaud is offline Super Moderator Power Poster
    Join Date
    Dec 2012
    Location
    England
    Posts
    6,814

    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++17 Compiler: Microsoft VS2019 (16.2.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
  •  


Windows Mobile Development Center


Click Here to Expand Forum to Full Width




On-Demand Webinars (sponsored)