CODEWITHSUNDEEP
javafunctionfor-loop
Kevin
Kevin

Reputation:

Refactor for loops into function

I've got this piece of java code:

int maxDigit = 4;
for(int a = 0; a <= maxDigit; a++)
{
  for(int b = 0; b <= maxDigit; b++)
  {
    if(b != a){
      for(int c = 0; c <= maxDigit; c++)
      {
        if(c != a && c != b)
        {
          for(int d = 0; d <= maxDigit; d++)
          {
            if(d != a && d != b && d != c)
            {
              for(int e = 0; e <= maxDigit; e++)
              {
                if(e != a && e != b && e != c && e != d)
                {
                  String temp = a + "" + b + "" + c + "" + d + "" + e;
                  System.out.println(temp);
                  permutations.add(Integer.parseInt(temp));
                }
              }
            }
          }
        }
      }
    }
  }
}

How can you transform this piece of code into a function?

The purpose is to generate permutations of the digits 0 to 9 and here in the code above it is from 0 to 4. And it seems easy to put it in a function but i couldn't find it immediately.

Upvotes: 1

Views: 942

Answers (4)

Apocalisp
Apocalisp

Reputation: 35054

This is a variant of the classic problem of getting all permutations of a string.

The induction your professor wants you to make is that this problem lends itself well to a solution that uses recursion.

The basic algorithm for the permutations of string s is as follows:

  1. Select the first item in s.
  2. Get all permutations of the other items in s (except the item selected).
  3. Prepend selected item to each permutation from step 2.
  4. Repeat for the next character of s.

Here's an efficient solution using the Functional Java library.

Import these...

import fj.F;
import fj.P2;
import fj.P1;
import fj.data.Stream;
import static fj.data.Stream.nil;
import static fj.data.Stream.cons;
import static fj.data.Stream.range;
import static fj.data.Enumerator.charEnumerator;
import static fj.data.Show.streamShow;
import static fj.data.Show.charShow;
import static fj.P2.map2_;

A recursive function to find permutations:

public Stream<Stream<Character>> permutations(final Stream<Character> s) {
  return selections(s).bind(
    new F<P2<Character, Stream<Character>>, Stream<Stream<Character>>>() {
      public Stream<Stream<Character>>()
        f(final P2<Character, Stream<Character>> ys) {
          return permutations(ys._2()).bind(cons(ys._1()));
        }
      });
}

A recursive function to select each element in turn:

public Stream<P2<Character, Stream<Character>>>
selections(final Stream<Character> s) {
  if (xs.isEmpty())
    return nil();
  else {
    final char x = xs.head();
    final Stream<Character> xs = s.tail()._1();
    return cons(P.p(x, xs),
      new P1<Stream<P2<Character, Stream<Character>>>>() {
        public Stream<P2<Character, Stream<Character>>> _1() { 
          return selections(xs).map(map2_().f(cons(x))));
        }
      });
  }
}

and then, to get all permutations of characters '0' through '9':

Show<Stream<Character>> s = streamShow(charShow);
for (Stream<Character> ps : permutations(range(charEnumerator, '0', '9'))) {
  System.out.println(s.showS(ps));
}

EDIT: This is actually a great use case for comonads. Using the latest trunk head of Functional Java, you can do this with the Zipper comonad, like so:

public static Stream<Stream<Character>> perms(Stream<Character> s) {
  Stream<Stream<Character>> r = single(Stream.<Character>nil());
  for (final Zipper<Character> z : fromStream(s))
    r = join(z.cobind(
      new F<Zipper<Character>, Stream<Stream<Character>>>() {
        public Stream<Stream<Character>> f(final Zipper<Character> zp) {
          return perms(zp.lefts().reverse().append(zp.rights())).map(compose(
            Stream.<Character>cons().f(zp.focus()),
              P.<Stream<Character>>p1()));
        }
      }).toStream());
  return r;
}

Upvotes: 4

toolkit
toolkit

Reputation: 50227

You could use an N-ary tree, with 4 branches at each point, recursively navigate the tree and step over branches where that node's digit had already been seen?

Upvotes: 0

Anton Gogolev
Anton Gogolev

Reputation: 115711

No code, but an algorithm should be as follows.

Suppose you want all permutations of 5 digits from 0 to 7. To do that:

  • Calculate j = decimal value of base-7 value of 100000 (1 + 5 zeroes)
  • Loop for i = 0; i < j; ++i, converting each i to base-7 system, optionally prepending with zeroes.

Upvotes: 0

cadrian
cadrian

Reputation: 7376

Fill the holes:

int[] indexes = { 0, 0, 0, 0, 0 };
addPermutations(maxDigit, indexes, 0, permutations);


void addPermutations(int max, int[] indexes, int currentIndex, List<Integer> permutations) {
    if (currentIndex == indexes.length) {
        // terminal case
        String temp = ...;
        System.out.println(temp);
        permutations.add(Integer.parseInt(temp));
    } else {
        // recursive case
        for (int i = 0; i <= max; i++) {
            if (... != i) {
                indexes[currentIndex] = i;
                addPermutations(max, indexes, currentIndex+1, permutations);
            }
        }
    }
}

Upvotes: 1

Related Questions