Difference between pages "10.39" and "9.1"
(Difference between pages)
Jump to navigation
Jump to search
(Created page with "== A Python Solution - O(1) == <PRE> import sys n = int(sys.argv[1]) OUT_TMP = "Min # of coins for covering %d: %d, coins used: %s" COINS = tuple(sorted((3, 4, 9, 20, 22, 23)...") |
(Created page with "== Algorithm == Given <code>a</code>, the input array, and <code>curr</code>, the derangement built up so far: # If <code>curr</code> represents a complete solution, print i...") |
||
Line 1: | Line 1: | ||
− | == | + | == Algorithm == |
− | |||
− | |||
− | |||
− | + | Given <code>a</code>, the input array, and <code>curr</code>, the derangement built up so far: | |
− | |||
− | |||
− | + | # If <code>curr</code> represents a complete solution, print it. | |
− | + | # Otherwise, examine all the possibilities for the next element of the derangement. The next element must come from the input array <code>a</code>. It must not already have been used so far (<code>!curr.contains(a[i]</code>), and it must not be the element at the same position in the input array (<code>i != curr.size()</code>). | |
− | + | ## For each remaining possibility, add it to the current derangement and recurse. | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | + | == Implementation in Java == | |
− | + | <pre> | |
− | + | public class DerangementGenerator { | |
+ | public void derangements(int[] a) { | ||
+ | d(a, new LinkedList<Integer>()); | ||
+ | } | ||
− | + | public void d(int[] a, LinkedList<Integer> curr) { | |
− | + | if (curr.size() == a.length) | |
− | + | print(curr); | |
− | + | else { | |
− | + | for (int i = 0; i < a.length; i++) { | |
− | + | if (!curr.contains(a[i]) && i != curr.size()) { | |
− | + | curr.addLast(a[i]); // O(1) | |
− | + | d(a, curr); | |
− | + | curr.removeLast(); // O(1) | |
− | + | } | |
− | + | } | |
+ | } | ||
+ | } | ||
− | + | public void print(List<Integer> l) { | |
− | + | for (int i = 0; i < l.size() - 1; i++) { | |
− | + | System.out.print(l.get(i) + ", "); | |
− | + | } | |
− | + | System.out.println(l.get(l.size() - 1)); | |
− | + | } | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
public static void main(String[] args) { | public static void main(String[] args) { | ||
− | + | if (args.length < 1) { | |
− | int | + | System.err.println("Usage: java DerangementGenerator N"); |
+ | System.exit(-1); | ||
+ | } | ||
+ | int n = Integer.parseInt(args[0]); | ||
− | + | DerangementGenerator dg = new DerangementGenerator(); | |
− | + | int[] a = new int[n]; | |
− | + | for (int i = 0; i < n; i++) { | |
− | + | a[i] = i + 1; | |
− | int[] | ||
− | for (int i = 0; i < | ||
− | |||
} | } | ||
− | |||
− | + | dg.derangements(a); | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
} | } | ||
} | } | ||
+ | </pre> | ||
− | + | Back to [[Chapter 9]] | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | Back to [[Chapter |
Latest revision as of 13:51, 21 September 2020
Algorithm
Given a
, the input array, and curr
, the derangement built up so far:
- If
curr
represents a complete solution, print it. - Otherwise, examine all the possibilities for the next element of the derangement. The next element must come from the input array
a
. It must not already have been used so far (!curr.contains(a[i]
), and it must not be the element at the same position in the input array (i != curr.size()
).- For each remaining possibility, add it to the current derangement and recurse.
Implementation in Java
public class DerangementGenerator { public void derangements(int[] a) { d(a, new LinkedList<Integer>()); } public void d(int[] a, LinkedList<Integer> curr) { if (curr.size() == a.length) print(curr); else { for (int i = 0; i < a.length; i++) { if (!curr.contains(a[i]) && i != curr.size()) { curr.addLast(a[i]); // O(1) d(a, curr); curr.removeLast(); // O(1) } } } } public void print(List<Integer> l) { for (int i = 0; i < l.size() - 1; i++) { System.out.print(l.get(i) + ", "); } System.out.println(l.get(l.size() - 1)); } public static void main(String[] args) { if (args.length < 1) { System.err.println("Usage: java DerangementGenerator N"); System.exit(-1); } int n = Integer.parseInt(args[0]); DerangementGenerator dg = new DerangementGenerator(); int[] a = new int[n]; for (int i = 0; i < n; i++) { a[i] = i + 1; } dg.derangements(a); } }
Back to Chapter 9