-
Notifications
You must be signed in to change notification settings - Fork 21
/
46.permutations.rb
89 lines (79 loc) · 1.77 KB
/
46.permutations.rb
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
# -*- coding: utf-8 -*-
#
# @lc app=leetcode id=46 lang=ruby
#
# [46] Permutations
#
# https://leetcode.com/problems/permutations/description/
#
# Given a collection of distinct integers, return all possible
# permutations.
#
# Example:
#
# Input: [1,2,3]
# Output:
# [
# [1,2,3],
# [1,3,2],
# [2,1,3],
# [2,3,1],
# [3,1,2],
# [3,2,1]
# ]
# See
# - https://en.wikipedia.org/wiki/Permutation
# - https://www.cs.princeton.edu/courses/archive/fall12/cos226/lectures/67CombinatorialSearch.pdf
#
# 1. Fix numbers up to given point k.
# 2. Permute the rest of it recursively.
#
# Example: given "xyz"
#
# - x followed by all permutations of y and z (yz and zy)
# - y followed by all permutations of x and z (xz and zx)
# - z followed by all permutations of x and y (xy and yx)
# @param {Integer[]} nums
# @return {Integer[][]}
def permute(nums, k=0, ans=[])
ans << nums.dup and return if k == nums.size
(k...nums.size).each do |i|
swap(nums, k, i) # fix nums[k] using nums[i]
permute(nums, k+1, ans) # permute the rest
swap(nums, k, i) # revert nums[k] to initial state
end
ans
end
def swap(nums, i, j)
nums[i], nums[j] = nums[j], nums[i]
end
# DFS+Backtracking.
def permute(nums, seen=Set.new, path=[], paths=[])
if path.size == nums.size
paths << path.dup
else
nums.each do |n|
next if seen.include?(n)
path << n
seen << n
permute(nums, seen, path, paths)
path.pop
seen.delete(n)
end
end
paths
end
# DFS.
def permute(nums, seen=Set.new, path=[], paths=[])
if path.size == nums.size
paths << path.dup
else
nums.each do |n|
next if seen.include?(n)
seen << n
permute(nums, seen, path+[n], paths)
seen.delete(n)
end
end
paths
end