46 Permutations ✅¶
Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.
Example 1:
Example 2:
Example 3:
C# Solution¶
using System;
using System.Collections.Generic;
namespace Algorithms.Medium
{
public class Permutation
{
public static List<List<int>> Permute(List<int> vs)
{
var result = new List<List<int>>();
bool[] visited = new bool[vs.Count];
DFSPermute(vs, result, new List<int>(), visited);
return result;
}
private static void DFSPermute(List<int> vs, List<List<int>> result, List<int> curr, bool[] visited)
{
if (curr.Count == vs.Count)
{
result.Add(new List<int>(curr));
return;
}
for (var i = 0; i < vs.Count; i++)
{
if (visited[i] == false)
{
visited[i] = true;
curr.Add(vs[i]);
DFSPermute(vs, result, curr, visited);
curr.RemoveAt(curr.Count - 1);
visited[i] = false;
}
}
}
}
}
C# Tests¶
using System.Collections.Generic;
using Algorithms.Medium;
using Xunit;
namespace AlgorithmTests.Medium
{
public class PermutationTests
{
[Fact]
public void PermuteTest1()
{
Assert.Equal(new List<List<int>> {
new List<int> { 1, 2, 3 },
new List<int> { 1, 3, 2 },
new List<int> { 2, 1, 3 },
new List<int> { 2, 3, 1 },
new List<int> { 3, 1, 2 },
new List<int> { 3, 2, 1 } }, Permutation.Permute(new List<int> { 1, 2, 3 }));
}
[Fact]
public void PermuteTest2()
{
Assert.Equal(new List<List<int>> {
new List<int> { 0, 1 },
new List<int> { 1, 0 } }, Permutation.Permute(new List<int> { 0, 1 }));
}
[Fact]
public void PermuteTest3()
{
Assert.Equal(new List<List<int>> {
new List<int> { 1 } }, Permutation.Permute(new List<int> { 1 }));
}
}
}
Note: without visited flag we can check the curr list itself¶
Follow-up : what if the given set contains duplicates?¶
It is very similar to subsets with duplicates problem, except the order of the list is required. Here, we allocate a new boolean array to keep track of whether an element has been used in backtracking.
(function (exports) {
'use strict';
var permutations = (function () {
var res;
function swap(arr, i, j) {
var temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
function permutations(arr, current) {
if (current >= arr.length) {
return res.push(arr.slice());
}
for (var i = current; i < arr.length; i += 1) {
swap(arr, i, current);
permutations(arr, current + 1);
swap(arr, i, current);
}
}
/**
* Finds all the permutations of given array.<br><br>
* Permutation relates to the act of rearranging, or permuting,
* all the members of a set into some sequence or order.
* For example there are six permutations of the set {1,2,3}, namely:
* (1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), and (3,2,1).<br><br>
* Complexity: O(N*N!).
*
* @example
*
* var permutations = require('path-to-algorithms/src/' +
* 'combinatorics/permutations').permutations;
* var result = permutations(['apple', 'orange', 'pear']);
*
* // [ [ 'apple', 'orange', 'pear' ],
* // [ 'apple', 'pear', 'orange' ],
* // [ 'orange', 'apple', 'pear' ],
* // [ 'orange', 'pear', 'apple' ],
* // [ 'pear', 'orange', 'apple' ],
* // [ 'pear', 'apple', 'orange' ] ]
* console.log(result);
*
* @module combinatorics/permutations
* @public
* @param {Array} arr Array to find the permutations of.
* @returns {Array} Array containing all the permutations.
*/
return function (arr) {
res = [];
permutations(arr, 0);
var temp = res;
// Free the extra memory
res = null;
return temp;
};
}());
exports.permutations = permutations;
}((typeof window === 'undefined') ? module.exports : window));