Difference between pages "10.39" and "9.1"

From The Algorithm Design Manual Solution Wiki
(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:
−
== A Python Solution - O(1) ==
+
== Algorithm ==
−
<PRE>
 
−
import sys
 
−
n = int(sys.argv[1])
 
  
−
OUT_TMP = "Min # of coins for covering %d: %d, coins used: %s"
+
Given <code>a</code>, the input array, and <code>curr</code>, the derangement built up so far:
−
COINS = tuple(sorted((3, 4, 9, 20, 22, 23), reverse=True))
 
−
FAILSAFE_MAX = 9999999999
 
  
−
if len(COINS) < 1: raise Exception("Coins please!")
+
# If <code>curr</code> represents a complete solution, print it.
−
if len(COINS) == 1:
+
# 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>).
−
    c = COINS[0]
+
## For each remaining possibility, add it to the current derangement and recurse.
−
    if n % c == 0:
 
−
        print OUT_TMP % (n, n/c, [c]*(n/c))
 
−
        sys.exit()
 
−
    else:
 
−
        raise Exception("Impossible!")
 
  
−
CAL_MAX = min(COINS[0] * COINS[1], n+1)
+
== Implementation in Java ==
  
−
min_coins_n = [0]
+
<pre>
−
min_coins_l = [()]
+
public class DerangementGenerator {
 +
    public void derangements(int[] a) {
 +
        d(a, new LinkedList<Integer>());
 +
    }
  
−
for i in xrange(1, CAL_MAX):
+
    public void d(int[] a, LinkedList<Integer> curr) {
−
    if i in COINS:
+
        if (curr.size() == a.length)
−
        min_coins_n.append(1)
+
            print(curr);
−
        min_coins_l.append((i,))
+
        else {
−
    else:
+
            for (int i = 0; i < a.length; i++) {
−
        current_min = -1
+
                if (!curr.contains(a[i]) && i != curr.size()) {
−
        for c in COINS:
+
                    curr.addLast(a[i]); // O(1)
−
            smaller_i = i - c
+
                    d(a, curr);
−
            if smaller_i > 0 and min_coins_n[smaller_i] < FAILSAFE_MAX and \
+
                    curr.removeLast(); // O(1)
−
              (current_min == -1 or min_coins_n[smaller_i] < min_coins_n[current_min]):
+
                 }
−
                 current_min = smaller_i
+
            }
 +
        }
 +
    }
  
−
        if current_min != -1:
+
    public void print(List<Integer> l) {
−
            min_coins_n.append(min_coins_n[current_min] + 1)
+
        for (int i = 0; i < l.size() - 1; i++) {
−
            l = list(min_coins_l[current_min]) # copy
+
             System.out.print(l.get(i) + ", ");
−
            l.append(i - current_min)
+
        }
−
            # another copy, not required but robuster code
+
        System.out.println(l.get(l.size() - 1));
−
            ll = tuple(l)
+
    }
−
            min_coins_l.append(tuple(l))
 
−
        else:
 
−
             # not changable using the current coins
 
−
            min_coins_n.append(FAILSAFE_MAX)
 
−
            min_coins_l.append(None)
 
−
 
 
−
big_part_n = 0
 
−
coins_list = []
 
−
remaining_n = n
 
−
if n > CAL_MAX:
 
−
    n_big_part = n - CAL_MAX
 
−
    big_part_n = (n_big_part / COINS[0]) + 1
 
−
    coins_list = [COINS[0]] * big_part_n
 
−
    remaining_n -= big_part_n * COINS[0]
 
−
 
 
−
final_n = big_part_n + min_coins_n[remaining_n]
 
−
if final_n >= FAILSAFE_MAX:
 
−
    raise Exception("Impossible!")
 
−
coins_list.extend(min_coins_l[remaining_n])
 
−
print OUT_TMP % (n, final_n, coins_list)
 
−
</PRE>
 
−
 
 
−
== A Java solution - O(n) ==
 
−
 
 
−
<PRE>
 
−
 
 
−
public class CoinProblem {
 
  
 
     public static void main(String[] args) {
 
     public static void main(String[] args) {
−
         int sumToMakeChangeFor = 20;
+
         if (args.length < 1) {
−
         int[] coinDenominations = new int[]{1, 2, 5, 10};
+
            System.err.println("Usage: java DerangementGenerator N");
 +
            System.exit(-1);
 +
        }
 +
         int n = Integer.parseInt(args[0]);
  
−
         System.out.println("Number of coins needed = " + numberOfCoinsNeededForChange(sumToMakeChangeFor, coinDenominations));
+
         DerangementGenerator dg = new DerangementGenerator();
−
    }
+
         int[] a = new int[n];
−
 
+
         for (int i = 0; i < n; i++) {
−
    private static int numberOfCoinsNeededForChange(int sum, int[] coinDenominations) {
+
             a[i] = i + 1;
−
         int[] minimumNumberOfCoinsNeeded = new int[sum + 1];
 
−
         for (int i = 0; i <= sum; i++){
 
−
             minimumNumberOfCoinsNeeded[i] = Integer.MAX_VALUE;
 
 
         }
 
         }
−
        minimumNumberOfCoinsNeeded[0] = 0;
 
  
−
         for (int currentSum = 1; currentSum <= sum; currentSum++) {
+
         dg.derangements(a);
−
            for (int j = 0; j < coinDenominations.length; j++) {
 
−
                if (coinDenominations[j] <= currentSum &&
 
−
                          ((minimumNumberOfCoinsNeeded[currentSum - coinDenominations[j]] + 1) < minimumNumberOfCoinsNeeded[currentSum]))
 
−
                    minimumNumberOfCoinsNeeded[currentSum] = minimumNumberOfCoinsNeeded[currentSum - coinDenominations[j]] + 1;
 
−
            }
 
−
        }
 
−
        return minimumNumberOfCoinsNeeded[sum];
 
 
     }
 
     }
 
}
 
}
 +
</pre>
  
  
−
 
+
Back to [[Chapter 9]]
−
</PRE>
 
−
 
 
−
Reference: [http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=dynProg Dynamic Programming, TopCoder.com]
 
−
 
 
−
 
 
−
Back to [[Chapter 10]]
 

Latest revision as of 13:51, 21 September 2020

Algorithm

Given a, the input array, and curr, the derangement built up so far:

  1. If curr represents a complete solution, print it.
  2. 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()).
    1. 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

Retrieved from "https://algorist.com//algowiki/index.php?title=10.39&oldid=398"