// TO DO: areEqual, toGrid, toUpsideDown, toMirrorImage.
import java.util.*;
final class Objects {
/** For grids that are not null, returns true if grid1 and grid2 are the same size
* and contain equal values; otherwise, returns false. Arrays (e.g. gridX, gridX[i])
* and elements of arrays (e.g. gridX[i], gridX[i][j]) may be null. A null array is
* considered to be equal to another null array; corresponding null elements are also
* considered to be equal. Values do not have to be the same object (i.e. stored at
* the same memory location) to be equal. See Objects.testAreEqual for examples.
*/
public static boolean areEqual(final Object[][] grid1, Object[][] grid2) {
if (grid1 == grid2) return true;
if (grid1 == null || grid2 == null) return false;
if (grid1.length != grid2.length) return false;
for (int i = grid1.length - 1; i >= 0; i--) {
final Object[] row1 = grid1[i], row2 = grid2[i];
if (row1 == row2) continue;
if (row1 == null || row2 == null) return false;
if (row1.length != row2.length) return false;
for (int j = row1.length -1; j >= 0; j--) {
if (!row1[j].equals(row2[j])) return false;
}
}
return true;
}
/** Converts listOfValues to an equivalent grid.
*/
public static Object[][] toGrid(final List<List<Object>> listOfLists) {
final int n = listOfLists.size();
final Object[][] grid = new Object[n][];
for (int i = 0; i < n; i++) {
List<Object> list = listOfLists.get(i);
final int m = list.size();
grid[i] = new Object[m];
for (int j = 0; j < m; j++) {
grid[i][j] = list.get(j);
}
}
return grid;
}
/** Returns a copy of grid with the rows in reverse order.
*/
public static Object[][] toUpsideDown(final Object[][] grid) {
final int n = grid.length;
final Object[][] upsideDown = new Object[n][];
for (int i = 0, j = n - 1; i < n; i++, j--) {
upsideDown[i] = grid[j];
}
return upsideDown;
}
/** Returns a copy of grid with the columns in reverse order.
*/
public static Object[][] toMirrorImage(final Object[][] grid) {
final int n = grid.length;
final Object[][] mirrorImage = new Object[n][];
for (int i = 0; i < n; i++) {
final Object[] row = grid[i];
final int m = row.length;
final Object[] copy = new Object[m];
mirrorImage[i] = copy;
for (int j = 0, k = m - 1; j < m; j++, k--) {
copy[j] = row[k];
}
}
return mirrorImage;
}
/** Returns a String representation of grid.
*/
public static String toString(final Object[][] grid) {
StringBuilder sb = new StringBuilder();
final int n = grid == null ? 0 : grid.length;
for (int i = 0; i < n; i++) {
final Object[] row = grid[i];
final int m = row != null ? row.length : 0;
sb.append("[");
if (m > 0) {
sb.append(row[0]);
}
for (int j = 1; j < m; j++) {
sb.append(", " + row[j].toString());
}
sb.append("]\n");
}
return sb.toString();
}
/** Returns a list of all permutations of series.
*/
public static List<List<Object>> toListOfPermutations(final Object[] series) {
List<List<Object>> allPerms;
final int seriesLen = series.length;
allPerms = new ArrayList<List<Object>>(1);
allPerms.add(new LinkedList<Object>());
if (seriesLen > 0) {
allPerms.get(0).add(series[0]);
}
for (int i = 1; i < seriesLen; i++) {
final Object item = series[i];
final int n = allPerms.size();
final List<List<Object>> morePerms;
morePerms = new ArrayList<List<Object>>(n*(n+1));
for (List<Object> perm : allPerms) {
final int permLen = perm.size();
for (int j = 0; j <= permLen; j++) {
final List<Object> nextPerm;
nextPerm = new LinkedList<Object>();
nextPerm.addAll(perm);
nextPerm.add(j, item);
morePerms.add(nextPerm);
}
}
allPerms = morePerms;
}
return allPerms;
/* AN ALTERNATIVE RECURSIVE SOLUTION
*
* I. The Base (Non-Recursive) Case.
*
* If the series has no elements, then there is only one possible
* permutation (the empty permutation); add it to the list of
* permutations.
*
* II. The Recursive Case.
*
* A. Solve a smaller instance of the problem.
*
* If the series has one or more elements, we recursively call
* toListOfPermutations, passing as the argument a subseries with one
* fewer element than series. (When there is a choice, it doesn't matter
* which element is excuded.)
*
* 1. Exclude, say, the first element; assign the value of the
* excluded element to a temporary variable for use in part B.
* 2. Create a new array of size one less than series; copy all
* of the elements except for the excluded element to the
* new array.
* 3. Call toListOfPermutations, passing the new array as the argument.
*
* B. In all possible ways, combine the excluded element with each
* permutation returned by the recusive call.
*
* For each permutation in the list of permutations returned (i.e
* for each list of values in the list of lists returned) the size
* of the permutation will be one less than series. For each integer
* i between zero and the size of the permutation inclusive:
*
* 1. Create a copy of the permutation, anticipating that an
* additional element will be added to the copy.
* 2. Add the excluded element from step 1 to the copy at index i.
* 3. Add the new permutation to the expanding list of permutations.
*
* III. Return the final list of permutations.
*
* EXAMPLE: https://apcsafreeresponsequestions.blogspot.com/2019/03/permuter.html
*/
}
/** Used to test the implementation of Objects.areEqual.
*/
public static void testAreEqual() {
// Two different String objects with the same value:
final String anA = new String("A"), anotherA = new String("A");
final String[] // Rows (arrays):
nullRow = null, rowOfNull = {null}, rowOfLen2 = {"B", "C"},
emptyRow = {}, rowOfAnA = {anA}, rowOfAnotherA = {anotherA};
final String[][] // Grids (arrays of arrays):
g0 = null,
g1 = {rowOfAnA},
g2 = g1,
g3 = {rowOfAnA},
g4 = {rowOfAnotherA},
g5 = {rowOfLen2},
g6 = {nullRow},
g7 = {rowOfNull},
g8 = {emptyRow},
g9 = {rowOfAnA, rowOfLen2},
g10 = {nullRow, rowOfNull, emptyRow, rowOfLen2, rowOfAnA},
g11 = {nullRow, rowOfNull, emptyRow, rowOfLen2, rowOfAnotherA};
// Print test grids:
System.out.println("g0:\n" + toString(g0));
System.out.println("g1:\n" + toString(g1));
System.out.println("g2:\n" + toString(g2));
System.out.println("g3:\n" + toString(g3));
System.out.println("g4:\n" + toString(g4));
System.out.println("g5:\n" + toString(g5));
System.out.println("g6:\n" + toString(g6));
System.out.println("g7:\n" + toString(g7));
System.out.println("g8:\n" + toString(g8));
System.out.println("g9:\n" + toString(g9));
System.out.println("g10:\n" + toString(g10));
System.out.println("g11:\n" + toString(g11));
// True (are equal):
testAreEqual("g0 equals g0", g0, g0, true);
testAreEqual("g1 equals g1", g1, g1, true);
testAreEqual("g1 equals g2", g1, g2, true);
testAreEqual("g1 equals g3", g1, g3, true);
testAreEqual("g1 equals g4", g1, g4, true);
testAreEqual("g10 equals g11", g10, g11, true);
// False (are not equal):
testAreEqual("g0 not equals g1", g0, g1, false);
testAreEqual("g0 not equals g6", g0, g6, false);
testAreEqual("g0 not equals g7", g0, g7, false);
testAreEqual("g0 not equals g8", g0, g8, false);
testAreEqual("g1 not equals g5", g1, g5, false);
testAreEqual("g1 not equals g6", g1, g6, false);
testAreEqual("g1 not equals g7", g1, g7, false);
testAreEqual("g1 not equals g8", g1, g8, false);
testAreEqual("g1 not equals g9", g1, g9, false);
testAreEqual("g6 not equals g7", g6, g7, false);
testAreEqual("g6 not equals g8", g6, g8, false);
testAreEqual("g7 not equals g8", g7, g8, false);
testAreEqual("g9 not equals g10", g9, g10, false);
}
private static void testAreEqual(
final String s, final String[][] g1, final String[][] g2, final boolean expected)
{
try {
System.out.print(s + ": ");
System.out.println(Objects.areEqual(g1, g2) == expected ? "pass" : "FAIL");
}
catch(final Exception e) {
System.out.println(e);
}
}
}
final public class Permutations {
public static void main(final String args[]) {
final List<List<Object>> lists = Objects.toListOfPermutations(args);
print(lists);
final Object[][] grid = Objects.toGrid(lists);
final Object[][] upsideDown = Objects.toUpsideDown(grid);
final Object[][] mirrorImage = Objects.toMirrorImage(grid);
System.out.println("Grid\n" + Objects.toString(grid));
System.out.println("Upside Down\n" + Objects.toString(upsideDown));
System.out.println("Mirror Image\n" + Objects.toString(mirrorImage));
System.out.print("Upside Down and Mirror Image are equal: ");
System.out.println(Objects.areEqual(upsideDown, mirrorImage));
System.out.println("\nTesting Objects.areEqual\n");
Objects.testAreEqual();
}
private static void print(final List<List<Object>> permutations) {
System.out.println("Permutations");
for (List<Object> permutation : permutations) {
System.out.println(permutation);
}
System.out.println();
}
}