Permutations

Definition

Definition

The Permutations Algorithm is a method used to generate all possible arrangements of elements in a set

Explanation

Recursively or iteratively generating permutations of elements in a set. At each step, it selects an element from the set and appends it to the current permutation. Then, it recursively generates permutations for the remaining elements until all elements have been used. The algorithm backtracks whenever it completes a permutation or reaches a dead-end, allowing it to explore all possible arrangements

Guidance

• Start with an empty permutation list
• Iterate through each element in the set
• For each element
  • Append it to the current permutation
  • Recursively generate permutations for the remaining elements
  • Backtrack to explore other possibilities
  • Repeat until all elements have been used
• Return the list of permutations

Tips

• use efficient data structures like arrays or lists to store permutations
• implement the algorithm using recursion for simplicity, but consider optimizing it with iteration for large sets
• utilize techniques like backtracking to efficiently explore all possible arrangements and avoid unnecessary computations

Practice

Practice

generate_permutations(elements, current_permutation, permutations):
  if length(current_permutation) == length(elements):
    permutations.append(current_permutation)
    return

  for each element in elements:
    if element not in current_permutation:
      new_permutation = current_permutation + [element]
      generate_permutations(elements, new_permutation, permutations)

Solution

package main

func permutations(nums []int) [][]int {
	var result [][]int
	var backtrack func(start int)
	backtrack = func(start int) {
		if start == len(nums) {
			temp := make([]int, len(nums))
			copy(temp, nums)
			result = append(result, temp)
			return
		}
		for i := start; i < len(nums); i++ {
			nums[i], nums[start] = nums[start], nums[i]
			backtrack(start + 1)
			nums[i], nums[start] = nums[start], nums[i]
		}
	}
	backtrack(0)
	return result
}

import java.util.ArrayList;
import java.util.List;

public class Permutations {

  public List<List<Integer>> permute(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();
    backtrack(nums, new ArrayList<>(), result);
    return result;
  }

  private void backtrack(int[] nums, List<Integer> temp, List<List<Integer>> result) {
    if (temp.size() == nums.length) {
      result.add(new ArrayList<>(temp));
      return;
    }
    for (int i = 0; i < nums.length; i++) {
      if (temp.contains(nums[i])) {
        continue;
      }
      temp.add(nums[i]);
      backtrack(nums, temp, result);
      temp.remove(temp.size() - 1);
    }
  }
}

function permutations(nums) {
  const result = [];

  function backtrack(temp) {
    if (temp.length === nums.length) {
      result.push([...temp]);
      return;
    }
    for (let num of nums) {
      if (!temp.includes(num)) {
        temp.push(num);
        backtrack(temp);
        temp.pop();
      }
    }
  }

  backtrack([]);
  return result;
}

fun permutations(nums: IntArray): List<List<Int>> {
    val result = mutableListOf<List<Int>>()
    fun backtrack(temp: MutableList<Int>) {
        if (temp.size == nums.size) {
            result.add(temp.toList())
            return
        }
        for (num in nums) {
            if (!temp.contains(num)) {
                temp.add(num)
                backtrack(temp)
                temp.removeAt(temp.size - 1)
            }
        }
    }
    backtrack(mutableListOf())
    return result
}

def permutations(nums):
    result = []

    def backtrack(temp):
        if len(temp) == len(nums):
            result.append(temp[:])
            return
        for num in nums:
            if num not in temp:
                temp.append(num)
                backtrack(temp)
                temp.pop()

    backtrack([])
    return result

fn permutations(nums: &mut Vec<i32>) -> Vec<Vec<i32>> {
    let mut result = Vec::new();

    fn backtrack(nums: &mut Vec<i32>, start: usize, result: &mut Vec<Vec<i32>>) {
        if start == nums.len() {
            result.push(nums.clone());
            return;
        }
        for i in start..nums.len() {
            nums.swap(start, i);
            backtrack(nums, start + 1, result);
            nums.swap(start, i);
        }
    }

    backtrack(nums, 0, &mut result);
    result
}

function permutations(nums: number[]): number[][] {
  const result: number[][] = [];

  function backtrack(temp: number[]) {
    if (temp.length === nums.length) {
      result.push([...temp]);
      return;
    }
    for (let num of nums) {
      if (!temp.includes(num)) {
        temp.push(num);
        backtrack(temp);
        temp.pop();
      }
    }
  }

  backtrack([]);
  return result;
}