Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

issue with permute_recursive #9014

Closed
DonMiller9294 opened this issue Aug 29, 2023 · 3 comments · Fixed by #9161
Closed

issue with permute_recursive #9014

DonMiller9294 opened this issue Aug 29, 2023 · 3 comments · Fixed by #9161
Labels
awaiting triage Awaiting triage from a maintainer

Comments

@DonMiller9294
Copy link

What would you like to share?

Your code looks mostly correct, but there's one issue in the permute_recursive function due to the modification of the nums list. Lists in Python are mutable, and when you use nums.pop(0), it modifies the original nums list. This can lead to incorrect results and even an infinite loop.

To fix this, you should pass a copy of the nums list to the recursive function. Here's the corrected permute_recursive function:

def permute_recursive(nums: list[int]) -> list[list[int]]:
"""
Return all permutations.

>>> permute_recursive([1, 2, 3])
[[3, 2, 1], [2, 3, 1], [1, 3, 2], [3, 1, 2], [2, 1, 3], [1, 2, 3]]
"""
result: list[list[int]] = []
if len(nums) == 0:
    return [[]]
for _ in range(len(nums)):
    n = nums.pop(0)
    permutations = permute_recursive(nums[:])  # Make a copy of nums
    for perm in permutations:
        perm.append(n)
    result.extend(permutations)
    nums.append(n)
return result

With this modification, your code should work correctly for both `permute_recursive` and `permute_backtrack`.

### Additional information

_No response_
@DonMiller9294 DonMiller9294 added the awaiting triage Awaiting triage from a maintainer label Aug 29, 2023
@Ayushrai001
Copy link

def generate_permutations(nums):
def backtrack(start):
if start == len(nums):
result.append(nums[:])
return
for i in range(start, len(nums)):
nums[start], nums[i] = nums[i], nums[start] # Swap elements
backtrack(start + 1)

Recurse

        nums[start], nums[i] = nums[i], nums[start]  # Backtrack
        
result = []
backtrack(0)
return result

Example usage

input_nums = [1, 2, 3]
permutations = generate_permutations(input_nums)
print(permutations)

@tianyizheng02
Copy link
Contributor

I think it's more readable to make the list copy using nums.copy(). Feel free to open a PR to make this fix.

@aryan1165
Copy link
Contributor

Hey. I have added a PR #9115 fixing this issue. As you mentioned, I have used nums.copy() to pass a copy of the nums list. Please review it. Thanks.

tianyizheng02 pushed a commit that referenced this issue Oct 1, 2023
* Fixes #9014

* Fixed permute_recursive() by passing nums.copy()
sedatguzelsemme pushed a commit to sedatguzelsemme/Python that referenced this issue Sep 15, 2024
@isidroas isidroas mentioned this issue Jan 25, 2025
14 tasks
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
awaiting triage Awaiting triage from a maintainer
Projects
None yet
Development

Successfully merging a pull request may close this issue.

4 participants