2
$\begingroup$

What would it be a recursive algorithm to get permutations for any list of n elements that might contain or not repeated elements?

For the following 3-element list [1, 1, 2] I would expect the following result:

[1, 1, 2]
[1, 2, 1]
[2, 1, 1]

So far I have the following result:

[1, 1, 2] <- duplicate
[1, 2, 1] <- duplicate
[1, 1, 2]
[1, 2, 1]
[2, 1, 1] <- duplicate
[2, 1, 1]

with algorithm below:

FUNCTION permute(array, nestingLevel) :
    FOR index = nestingLevel TO array size -1
        SWAP array[index] WITH array[nestingLevel]
        CALL permute (array, nestingLevel + 1)
        SWAP array[nestingLevel] WITH array[index]
    END FOR

    IF recursionNestingLevel EQUAL TO array size - 1
        PRINT array
    END IF
END FUNCTION

DEFINE array[] := 1, 1, 2
CALL permute (array, 0)
$\endgroup$
1
  • $\begingroup$ Does that mean that I should change the place and condition where I print the results? Because the Idea of the algorithm I have is that it goes all the way through and swaps, and prints while coming back from recursion but outside the loop with no visibility of anything else but the nesting level. Do you have pseudocode representation by any chance? $\endgroup$ Mar 30, 2019 at 14:34

1 Answer 1

2
$\begingroup$

I will change your function a bit, because there is too much going on with swaps and there is variable recursionNestingLevel which is not really declared or needed.

FUNCTION permute(array, nestingLevel) :
    IF nestingLevel EQUAL TO array size
        PRINT array
        RETURN
    END IF

    CALL permute (array, nestingLevel + 1)

    SET index TO nestingLevel + 1
    WHILE index LESS THAN array size
        SWAP array[index] WITH array[nestingLevel]
        CALL permute (array, nestingLevel + 1)
        INCREMENT index BY 1
    ENDWHILE
END FUNCTION

DEFINE array[] := 1, 1, 2
CALL permute (array, 0)

Now there is a simple idea to prevent recursing over same elements - it eliminates first unnecessary swap of and all redundant calls when array[index] is equal array[nesting level]:

FUNCTION permute(array, nestingLevel) :
    IF nestingLevel EQUAL TO array size
        PRINT array
        RETURN
    END IF

    CALL permute (array, nestingLevel + 1)

    SET index TO nestingLevel + 1
    WHILE index LESS THAN array size
+       IF array[index] EQUAL array[nestingLevel] CONTINUE
+       array = CLONE array
        SWAP array[index] WITH array[nestingLevel]
        CALL permute (array, nestingLevel + 1)
        INCREMENT index BY 1
    ENDWHILE
END FUNCTION

DEFINE array[] := 1, 1, 2
CALL permute (array, 0)

CLONE here prevents passing by reference of array, which would propagate changes to every recursive call

When you prevent swapping same elements and calling permute, it effectively blocks call with same parameters, so there are no duplicates.
BTW I have tested this code, for [1, 1, 2] it yields [ 1, 1, 2 ], [ 1, 2, 1 ], [ 2, 1, 1 ], with JavaScript

$\endgroup$
5
  • $\begingroup$ Hi @Evil. I implemented the code and it didn't work with different data other than [1,1,2]. I added "PRINT array" to the proposed answer because only one element (first one) was being printed. $\endgroup$ Apr 1, 2019 at 3:22
  • $\begingroup$ I did a literal translation to Java. It prints one permutation so just added that small detail. $\endgroup$ Apr 1, 2019 at 3:42
  • $\begingroup$ The code works, I added + 1 to the FOR index = nestingLevel + 1 and removed the -1 from IF nestingLevel EQUAL TO array size -1 because they were misleading. Also removed the unnecessary print statement I added, apologize. $\endgroup$ Apr 1, 2019 at 5:04
  • 1
    $\begingroup$ If I compare the results of my code against your code they return different results but if I remove the a = a.slice() from your code, both results are identical. Could you please express the a = a.slice() (I used Object.clone() in Java) in pseudocode to maintain the pseudocode independent from implementation to accept the answer? It looks like the way to avoid the over-swapping of one code version is instantiating copies of objects which it's a very interesting feature $\endgroup$ Apr 1, 2019 at 5:26
  • $\begingroup$ @CamelCamelius I have added changes. There is Object.clone in both J and JS which works exactly the same: both are shallow copy. Slice in my code is shallow copy for arrays. $\endgroup$
    – Evil
    Apr 1, 2019 at 12:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.