Package: PermuteArray

PermuteArray

nameinstructionbranchcomplexitylinemethod
PermuteArray(int)
M: 5 C: 16
76%
M: 1 C: 1
50%
M: 1 C: 1
50%
M: 1 C: 6
86%
M: 0 C: 1
100%
getFactorial(int)
M: 0 C: 13
100%
M: 0 C: 2
100%
M: 0 C: 2
100%
M: 0 C: 1
100%
M: 0 C: 1
100%
getNumLeft()
M: 3 C: 0
0%
M: 0 C: 0
100%
M: 1 C: 0
0%
M: 1 C: 0
0%
M: 1 C: 0
0%
getTotal()
M: 3 C: 0
0%
M: 0 C: 0
100%
M: 1 C: 0
0%
M: 1 C: 0
0%
M: 1 C: 0
0%
hasNext()
M: 0 C: 9
100%
M: 0 C: 2
100%
M: 0 C: 2
100%
M: 0 C: 1
100%
M: 0 C: 1
100%
next()
M: 0 C: 112
100%
M: 0 C: 8
100%
M: 0 C: 5
100%
M: 0 C: 22
100%
M: 0 C: 1
100%
reset()
M: 0 C: 19
100%
M: 0 C: 2
100%
M: 0 C: 2
100%
M: 0 C: 4
100%
M: 0 C: 1
100%

Coverage

1: /*******************************************************************************
2: *
3: *        Copyright (C) 2008, 2009 Fujitsu Services Ltd.
4: *
5: *        Author: Nick Battle
6: *
7: *        This file is part of VDMJ.
8: *
9: *        VDMJ is free software: you can redistribute it and/or modify
10: *        it under the terms of the GNU General Public License as published by
11: *        the Free Software Foundation, either version 3 of the License, or
12: *        (at your option) any later version.
13: *
14: *        VDMJ is distributed in the hope that it will be useful,
15: *        but WITHOUT ANY WARRANTY; without even the implied warranty of
16: *        MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17: *        GNU General Public License for more details.
18: *
19: *        You should have received a copy of the GNU General Public License
20: *        along with VDMJ. If not, see <http://www.gnu.org/licenses/>.
21: *
22: ******************************************************************************/
23:
24: // Based on source from http://www.merriampark.com/perm.htm
25:
26: package org.overture.codegen.runtime.traces;
27:
28: public class PermuteArray
29: {
30:         private int[] a;
31:         private long numLeft;
32:         private long total;
33:
34:         // -----------------------------------------------------------
35:         // Constructor. WARNING: Don't make n too large.
36:         // Recall that the number of permutations is n!
37:         // which can be very large, even when n is as small as 20 --
38:         // 20! = 2,432,902,008,176,640,000 and
39:         // 21! is too big to fit into a Java long, which is
40:         // why we use BigInteger instead.
41:         // ----------------------------------------------------------
42:
43:         public PermuteArray(int n)
44:         {
45:•                if (n < 1)
46:                 {
47:                         throw new IllegalArgumentException("Min 1");
48:                 }
49:
50:                 a = new int[n];
51:                 total = getFactorial(n);
52:                 reset();
53:         }
54:
55:         public void reset()
56:         {
57:•                for (int i = 0; i < a.length; i++)
58:                 {
59:                         a[i] = i;
60:                 }
61:
62:                 numLeft = total;
63:         }
64:
65:         // ------------------------------------------------
66:         // Return number of permutations not yet generated
67:         // ------------------------------------------------
68:
69:         public long getNumLeft()
70:         {
71:                 return numLeft;
72:         }
73:
74:         // ------------------------------------
75:         // Return total number of permutations
76:         // ------------------------------------
77:
78:         public long getTotal()
79:         {
80:                 return total;
81:         }
82:
83:         // -----------------------------
84:         // Are there more permutations?
85:         // -----------------------------
86:
87:         public boolean hasNext()
88:         {
89:•                return numLeft > 0;
90:         }
91:
92:         // ------------------
93:         // Compute factorial
94:         // ------------------
95:
96:         private static long getFactorial(int n)
97:         {
98:•                return n == 1 ? 1 : n * getFactorial(n - 1);
99:         }
100:
101:         // --------------------------------------------------------
102:         // Generate next permutation (algorithm from Rosen p. 284)
103:         // --------------------------------------------------------
104:
105:         public int[] next()
106:         {
107:•                if (numLeft == total)
108:                 {
109:                         numLeft = numLeft - 1;
110:                         return a;
111:                 }
112:
113:                 int temp;
114:
115:                 // Find largest index j with a[j] < a[j+1]
116:
117:                 int j = a.length - 2;
118:
119:•                while (a[j] > a[j + 1])
120:                 {
121:                         j--;
122:                 }
123:
124:                 // Find index k such that a[k] is smallest integer
125:                 // greater than a[j] to the right of a[j]
126:
127:                 int k = a.length - 1;
128:
129:•                while (a[j] > a[k])
130:                 {
131:                         k--;
132:                 }
133:
134:                 // Interchange a[j] and a[k]
135:
136:                 temp = a[k];
137:                 a[k] = a[j];
138:                 a[j] = temp;
139:
140:                 // Put tail end of permutation after jth position in increasing order
141:
142:                 int r = a.length - 1;
143:                 int s = j + 1;
144:
145:•                while (r > s)
146:                 {
147:                         temp = a[s];
148:                         a[s] = a[r];
149:                         a[r] = temp;
150:                         r--;
151:                         s++;
152:                 }
153:
154:                 numLeft = numLeft - 1;
155:                 return a;
156:         }
157: }