Last active
April 20, 2016 06:46
-
-
Save sshark/6350221 to your computer and use it in GitHub Desktop.
Search all the permutations that uniquely filled the blanks (0-slot) with the numbers from 1 to 9.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
package org.teckhooi; | |
import java.util.*; | |
/** | |
* @author Lim, Teck Hooi | |
*/ | |
public class Permutations { | |
public static void main(String[] args) { | |
List<Integer> series = Arrays.asList(new Integer[] {1, 0, 0, 5, 2, 0, 3, 0, 0}); | |
List<List<Integer>> permutations = permutationsFor(series); | |
prettyPrint(permutations); | |
System.out.println(permutations.size()); | |
} | |
private static void prettyPrint(List<List<Integer>> results) { | |
for (List<Integer> series : results) { | |
System.out.print("["); | |
StringBuilder buffer = new StringBuilder(); | |
for (Integer i : series) { | |
buffer.append(i + ", "); | |
} | |
buffer.setLength(buffer.length() - 2); | |
System.out.println(buffer.toString() + "]"); | |
} | |
} | |
private static List<List<Integer>> permutationsFor(List<Integer> series) { | |
Set<Integer> availableNums = new HashSet<>(Arrays.asList(new Integer[] {1, 2, 3, 4, 5, 6, 7, 8, 9})); | |
availableNums.removeAll(series); | |
return permutationsFor(series, availableNums); | |
} | |
private static List<List<Integer>> permutationsFor(List<Integer> series, Set<Integer> availableNums) { | |
List<List<Integer>> allSeries = new ArrayList<>(); | |
if (availableNums.isEmpty()) { | |
allSeries.add(series); | |
return allSeries; | |
} else { | |
for (Integer num : availableNums) { | |
Set<Integer> newAvailableNums = new HashSet<>(availableNums); | |
newAvailableNums.remove(num); | |
List<Integer> newSeries = new ArrayList<>(series); | |
newSeries.set(series.indexOf(0), num); | |
for (List<Integer> result : permutationsFor(newSeries, newAvailableNums)) { | |
allSeries.add(result); | |
} | |
} | |
} | |
return allSeries; | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
package org.teckhooi; | |
import scala.annotation.tailrec | |
object Permutations { | |
def search(xs: Seq[Int], ys: Seq[Int] = 1 to 9): Seq[Seq[Int]] = ys.diff(xs) match { | |
case Nil => Seq(xs) | |
case zs => zs.flatMap(z => search(xs.updated(xs.indexOf(0),z),zs)) | |
} | |
def waysToArr(l : List[Int]) = { | |
@tailrec | |
def _fac(i : BigInt, acc : BigInt) : BigInt = { | |
if (i == 0) acc | |
else _fac(i - 1, i * acc) | |
} | |
_fac(l.count(_ == 0), 1) | |
} | |
def main(args: Array[String]): Unit = { | |
val l = List(1, 0, 0, 5, 2, 0, 3, 0, 0) | |
val r = search(l) | |
if (r.size == waysToArr(l)) r.foreach(println) else println("Incorrect sequence given.") | |
println("Total number of permutations are " + r.size) | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Implemented a Java version of the function search(...).
To run Permutations.scala,
scalac Permutations.scala
scala org.teckhooi.Permutations
Permutations.scala is not a Scala script, therefore
scala Permutations.scala
will not run properly. Some modifications are required.