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%
main(String[])
M: 15 C: 0
0%
M: 2 C: 0
0%
M: 2 C: 0
0%
M: 4 C: 0
0%
M: 1 C: 0
0%
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.interpreter.traces;
27:
28: import java.util.Arrays;
29:
30: public class PermuteArray
31: {
32:         private int[] a;
33:         private long numLeft;
34:         private long total;
35:
36:         // -----------------------------------------------------------
37:         // Constructor. WARNING: Don't make n too large.
38:         // Recall that the number of permutations is n!
39:         // which can be very large, even when n is as small as 20 --
40:         // 20! = 2,432,902,008,176,640,000 and
41:         // 21! is too big to fit into a Java long, which is
42:         // why we use BigInteger instead.
43:         // ----------------------------------------------------------
44:
45:         public PermuteArray(int n)
46:         {
47:•                if (n < 1)
48:                 {
49:                         throw new IllegalArgumentException("Min 1");
50:                 }
51:
52:                 a = new int[n];
53:                 total = getFactorial(n);
54:                 reset();
55:         }
56:
57:         public void reset()
58:         {
59:•                for (int i = 0; i < a.length; i++)
60:                 {
61:                         a[i] = i;
62:                 }
63:
64:                 numLeft = total;
65:         }
66:
67:         // ------------------------------------------------
68:         // Return number of permutations not yet generated
69:         // ------------------------------------------------
70:
71:         public long getNumLeft()
72:         {
73:                 return numLeft;
74:         }
75:
76:         // ------------------------------------
77:         // Return total number of permutations
78:         // ------------------------------------
79:
80:         public long getTotal()
81:         {
82:                 return total;
83:         }
84:
85:         // -----------------------------
86:         // Are there more permutations?
87:         // -----------------------------
88:
89:         public boolean hasNext()
90:         {
91:•                return numLeft > 0;
92:         }
93:
94:         // ------------------
95:         // Compute factorial
96:         // ------------------
97:
98:         private static long getFactorial(int n)
99:         {
100:•                return n == 1 ? 1 : n * getFactorial(n - 1);
101:         }
102:
103:         // --------------------------------------------------------
104:         // Generate next permutation (algorithm from Rosen p. 284)
105:         // --------------------------------------------------------
106:
107:         public int[] next()
108:         {
109:•                if (numLeft == total)
110:                 {
111:                         numLeft = numLeft - 1;
112:                         return a;
113:                 }
114:
115:                 int temp;
116:
117:                 // Find largest index j with a[j] < a[j+1]
118:
119:                 int j = a.length - 2;
120:
121:•                while (a[j] > a[j + 1])
122:                 {
123:                         j--;
124:                 }
125:
126:                 // Find index k such that a[k] is smallest integer
127:                 // greater than a[j] to the right of a[j]
128:
129:                 int k = a.length - 1;
130:
131:•                while (a[j] > a[k])
132:                 {
133:                         k--;
134:                 }
135:
136:                 // Interchange a[j] and a[k]
137:
138:                 temp = a[k];
139:                 a[k] = a[j];
140:                 a[j] = temp;
141:
142:                 // Put tail end of permutation after jth position in increasing order
143:
144:                 int r = a.length - 1;
145:                 int s = j + 1;
146:
147:•                while (r > s)
148:                 {
149:                         temp = a[s];
150:                         a[s] = a[r];
151:                         a[r] = temp;
152:                         r--;
153:                         s++;
154:                 }
155:
156:                 numLeft = numLeft - 1;
157:                 return a;
158:         }
159:
160:         public static void main(String[] args)
161:         {
162:                 PermuteArray p = new PermuteArray(4);
163:
164:•                while (p.hasNext())
165:                 {
166:                         System.out.println(Arrays.toString(p.next()));
167:                 }
168:         }
169: }