String Ordered Permutation Algorithm Problem

String Permutation Problem

The algorithm problem goes something like this:

If you are given a character and its possible substitution set, then write a function that would print all the permutation of its characters.

Eg.

Given word “java”

Substitution Set =>
j [“J”, “7”]
a [“@”, “J”, “9”]
v [“V”, “^”]

Based on this, the possible permutations could be: J@V@, 7JV9..

Here is my approach using java


package com.gullele;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 
 * @author kaleb@gullele.com
 *
 */
public class PassPermutation {
	
	/**
	 * Holds the result of the permutation
	 */
	private List result;
	
	/**
	 * 
	 * @param args
	 */
	public static void main(String[] args) {
		PassPermutation word = new PassPermutation();
		word.initializeResult();
		
		List words = word.wordToListMapper("java");
	
		word.permuteIt("", words, 0);
		
		for (String str : word.result) {
			System.out.println(str);;
		}
	}
	
	/**
	 * Recursive function to handle the permutation.
	 * @param words
	 */
	private void permuteIt(String part, List words, int index) {
		int size = words.size();
		if (index == size-1) {
			String word = words.get(words.size()-1);
			for (int i=0 ; i < word.length() ; i++) {
				this.result.add(part + word.charAt(i));
			}
		} else {
			String word = words.get(index);
			index++;
			for (int j=0 ; j < word.length() ; j++) {
				part += word.charAt(j);
				permuteIt(part, words, index);
				part = part.substring(0, part.length()-1);
			}
		}
	}
	
	private void initializeResult() {
		this.result = new ArrayList();
	}
	
	/**
	 * A word to its combination mapping
	 * @param word
	 * @return
	 */
	private List wordToListMapper(String word) {

		Map mapper = this.dictionary();
		List mapped = new ArrayList();
		
		for (Character c:word.toCharArray()) {
			if (mapper.containsKey(c)) {
				mapped.add(mapper.get(c));
			}
		}
		
		return mapped;
	}
	
	/**
	 * A mapping dictionary.
	 * @return
	 */
	private Map dictionary() {
		
		Map mapper = new HashMap();
		mapper.put('j', "J7");
		mapper.put('a', "@J9");
		mapper.put('v', "v^");
		
		return mapper;
	}
}

Check if two strings are anagrams or not

Java Tomcat error: can not access a member of class with modifiers

pass all the jars in classpath when compiling java

Find K Complementary numbers from array Java implementation

Find longest palindrom from sequence of characters

Maven error Annotations are not supported in -source 1.3

Leave a Reply

Your email address will not be published. Required fields are marked *

*
*