Combinatorial Algorithms
import java.util.Arrays;
public class Main {
// Main function: The driver function
public static void main(String[] args) {
CombinatorialAlgorithms c = new CombinatorialAlgorithms();
c.initialize();
c.generateCombinatorialObjects();
}
}
class CombinatorialAlgorithms {
private static int MAX = 50;
private int item[] = new int[MAX];
private int count[] = new int[MAX];
private int R[] = new int[MAX];
private int u, n, r;
private enum Algorithm { PERMUTATIONS, SUBSETS, COMPOSITIONS, DIOPHANTINE, PARENTHESIS, NQUEENS, DERANGEMENTS, SUBSETSGRAYCODE, SUBSETSBINARY, PALINDROMES }
private Algorithm algo;
private String name;
private int nqueenscol[] = new int[MAX];
private int nqueensleftdiag[] = new int[MAX];
private int nqueensrightdiag[] = new int[MAX];
public void initialize() {
for (int i = 0; i < MAX; i++) { item[i] = i; count[i] = 1; }
//algo = Algorithm.PERMUTATIONS; name = "Permutations";
//algo = Algorithm.SUBSETS; name = "Subsets";
//algo = Algorithm.COMPOSITIONS; name = "Compositions";
//algo = Algorithm.DIOPHANTINE; name = "Diophantine";
//algo = Algorithm.PARENTHESIS; name = "Parenthesis";
//algo = Algorithm.NQUEENS; name = "nQueens";
//algo = Algorithm.DERANGEMENTS; name = "Derangements";
//algo = Algorithm.SUBSETSGRAYCODE; name = "Subsets gray code";
//algo = Algorithm.SUBSETSBINARY; name = "Subsets binary";
algo = Algorithm.PALINDROMES; name = "Palindromes";
switch (algo) {
case PERMUTATIONS: {
u = 2;
count[1] = 2;
count[2] = 2;
r = 3;
break;
}
case SUBSETS: {
u = 3;
count[1] = 1;
count[2] = 2;
count[3] = 1;
n = count[1] + count[2] + count[3];
break;
}
case COMPOSITIONS: {
/*
n = 4;
u = 4;
for (int i = 1; i <= u; i++)
count[i] = n / i;
*/
n = 7;
u = 3;
count[1] = 4; // non-optimal
count[2] = 2; // non-optimal
count[3] = 2; // optimal
break;
}
case DIOPHANTINE: {
n = 24;
u = 2;
item[1] = 2;
item[2] = 3;
count[1] = n / item[1];
count[2] = n / item[2];
break;
}
case PARENTHESIS: {
n = 3;
u = 2;
count[1] = 3;
count[2] = 3;
break;
}
case NQUEENS: {
n = 4;
for (int i = 1; i <= n; i++)
nqueenscol[i] = 1;
for (int i = 1; i <= 2 * n - 1; i++) {
nqueensleftdiag[i] = 1;
nqueensrightdiag[i] = 1;
}
break;
}
case DERANGEMENTS: {
u = 3;
count[1] = 1;
count[2] = 2;
count[3] = 2;
r = 3;
break;
}
case SUBSETSGRAYCODE: {
u = 3;
for (int i = 1; i <= u; i++)
count[i] = 0;
break;
}
case SUBSETSBINARY: {
u = 3;
for (int i = 1; i <= u; i++)
count[i] = 1;
break;
}
case PALINDROMES: {
u = 3;
for (int i = 1; i <= u; i++) { item[i] = i; count[i] = 2; }
// odd-sized palindromes
// r = 3;
// even-sized palindromes
r = 4;
break;
}
}
}
public void print(int[] arr, int size) {
for (int i = 1; i <= size; i++)
System.out.print(arr[i] + " ");
System.out.println();
}
public void generateCombinatorialObjects() {
System.out.println(name + " algorithm.");
switch (algo) {
case PERMUTATIONS: { permutations(1); break; }
case SUBSETS: { subsets(1); break; }
case COMPOSITIONS: { compositions(1); break; }
case DIOPHANTINE: { diophantine(1); break; }
case PARENTHESIS: { parenthesis(1); break; }
case NQUEENS: { nqueens(1); break; }
case DERANGEMENTS: { derangements(1); break; }
case SUBSETSGRAYCODE:{ subsetsgraycode(1);break; }
case SUBSETSBINARY: { subsetsbinary(1); break; }
case PALINDROMES: { palindromes(1); break; }
}
}
public void permutations(int depth) {
if (depth > r) { print(R, depth - 1); return; }
for (int i = 1; i <= u; i++) {
if (count[i] >= 1) {
R[depth] = item[i];
count[i]--;
permutations(depth + 1);
count[i]++;
}
}
}
public void subsets(int depth) {
print(R, depth - 1);
if (depth > n) return;
for (int i = 1; i <= u; i++) {
if (count[i] >= 1 && (depth == 1 || item[i] >= R[depth - 1])) {
R[depth] = item[i];
count[i]--;
subsets(depth + 1);
count[i]++;
}
}
}
public void compositions(int depth) {
if (n == 0) { print(R, depth - 1); return; }
for (int i = 1; i <= u; i++) {
if (count[i] >= 1 && n >= item[i]) {
R[depth] = item[i];
n = n - item[i];
count[i]--;
compositions(depth + 1);
count[i]++;
n = n + item[i];
}
}
}
public void diophantine(int depth) {
if (depth == (u + 1) && n != 0) return;
else if (depth == (u + 1) && n == 0) { print(R, depth - 1); return; }
for (int i = 0; i <= count[depth]; i++) {
if (n >= i * item[depth]) {
R[depth] = i;
n = n - i * item[depth];
diophantine(depth + 1);
n = n + i * item[depth];
}
}
}
public void parenthesis(int depth) {
if (depth > 2 * n) { print(R, depth - 1); return; }
for (int i = 1; i <= 2; i++) {
if (count[i] >= 1 && (i == 1 || count[2] > count[1])) {
R[depth] = i;
count[i]--;
parenthesis(depth + 1);
count[i]++;
}
}
}
public void nqueens(int depth) {
if (depth > n) { print(R, depth - 1); return; }
for (int i = 1; i <= n; i++) {
if (nqueenscol[i] == 1 && nqueensleftdiag[n + depth - i] == 1 && nqueensrightdiag[depth + i - 1] == 1) {
R[depth] = i;
nqueenscol[i]--;
nqueensleftdiag[n + depth - i]--;
nqueensrightdiag[depth + i - 1]--;
nqueens(depth + 1);
nqueenscol[i]++;
nqueensleftdiag[n + depth - i]++;
nqueensrightdiag[depth + i - 1]++;
}
}
}
public void derangements(int depth) {
if (depth > r) { print(R, depth - 1); return; }
for (int i = 1; i <= u; i++) {
if (count[i] >= 1 && item[i] != depth) {
R[depth] = item[i];
count[i]--;
derangements(depth + 1);
count[i]++;
}
}
}
public void subsetsgraycode(int depth) {
if (depth > u) { print(R, depth - 1); return; }
for (int i = 0; i <= 1; i++) {
R[depth] = (i == 0) ? count[depth] : (1 - count[depth]);
count[depth + 1] = count[depth + 1] + i;
subsetsgraycode(depth + 1);
count[depth + 1] = count[depth + 1] - i;
}
}
public void subsetsbinary(int depth) {
if (depth > u) { print(R, depth - 1); return; }
for (int i = 0; i <= 1; i++) {
if (count[depth] == 1) {
R[depth] = i;
count[depth]--;
subsetsbinary(depth + 1);
count[depth]++;
}
}
}
public void palindromes(int depth) {
if (depth == r/2 + 1) {
if (r % 2 == 1) {
for (int i = 1; i <= u; i++) {
if (count[i] >= 1) {
R[depth] = item[i];
print(R, r);
}
}
}
else
print(R, r);
return;
}
for (int i = 1; i <= u; i++) {
if (count[i] >= 2) {
R[depth] = R[r - depth + 1] = item[i];
count[i] = count[i] - 2;
palindromes(depth + 1);
count[i] = count[i] + 2;
}
}
}
}