Find the missing permutation: Difference between revisions
Content added Content deleted
(Link to topically related task) |
|||
Line 426: | Line 426: | ||
<lang J> ((i.!4) A. 'ABCD') -. data |
<lang J> ((i.!4) A. 'ABCD') -. data |
||
DBAC</lang> |
DBAC</lang> |
||
=={{header|Java}}== |
|||
'''optimized''' |
|||
<lang javascript>import java.util.ArrayList; |
|||
import java.util.Collections; |
|||
public class Utils<T extends Comparable<T>> { |
|||
private void swap(ArrayList<T> data, int i, int j) { |
|||
T t = data.get(i); |
|||
data.set(i, data.get(j)); |
|||
data.set(j, t); |
|||
} |
|||
public ArrayList<Integer> mRange(int from, int to) { |
|||
ArrayList<Integer> result = new ArrayList<Integer>(); |
|||
for (int i = from; i <= to; i++) |
|||
result.add(i); |
|||
return result; |
|||
} |
|||
public boolean nextPerm(ArrayList<T> data) { |
|||
// find the swaps |
|||
int c = -1, d = data.size(); |
|||
for (int i = d - 2; i >= 0; i--) |
|||
if (data.get(i).compareTo(data.get(i + 1)) < 0) { |
|||
c = i; |
|||
break; |
|||
} |
|||
if (c < 0) |
|||
return false; |
|||
int s = c + 1; |
|||
for (int j = c + 2; j < d; j++) |
|||
if (data.get(j).compareTo(data.get(s)) < 0 && // |
|||
data.get(j).compareTo(data.get(c)) > 0) |
|||
s = j; |
|||
// do the swaps |
|||
swap(data, c, s); |
|||
while (--d > ++c) |
|||
swap(data, c, d); |
|||
return true; |
|||
} |
|||
@SuppressWarnings("unchecked") |
|||
public ArrayList<ArrayList<T>> Permutations(ArrayList<T> d) { |
|||
ArrayList<ArrayList<T>> result = new ArrayList<ArrayList<T>>(); |
|||
Collections.sort(d); |
|||
do { |
|||
result.add((ArrayList<T>) d.clone()); |
|||
} while (this.nextPerm(d)); |
|||
return result; |
|||
} |
|||
}</lang> |
|||
And code: |
|||
<lang javascript>import java.util.ArrayList; |
|||
import com.google.common.base.Joiner; |
|||
import com.google.common.collect.ImmutableSet; |
|||
import com.google.common.collect.Lists; |
|||
public class FindMissingPermutation { |
|||
public static void main(String[] args) { |
|||
Utils<Character> u = new Utils<Character>(); |
|||
Joiner joiner = Joiner.on("").skipNulls(); |
|||
ArrayList<Character> c = Lists.newArrayList('A', 'B', 'C', 'D'); |
|||
ImmutableSet<String> s = ImmutableSet.of("ABCD", "CABD", "ACDB", |
|||
"DACB", "BCDA", "ACBD", "ADCB", "CDAB", "DABC", "BCAD", "CADB", |
|||
"CDBA", "CBAD", "ABDC", "ADBC", "BDCA", "DCBA", "BACD", "BADC", |
|||
"BDAC", "CBDA", "DBCA", "DCAB"); |
|||
for (ArrayList<Character> cs : u.Permutations(c)) |
|||
if (!s.contains(joiner.join(cs))) |
|||
System.out.println(joiner.join(cs)); |
|||
} |
|||
}</lang> |
|||
Output: DBAC |
|||
=={{header|JavaScript}}== |
=={{header|JavaScript}}== |