개발이 하고 싶어요

# Middle Permutation

Task

You are given a string s. Every letter in s appears once.

Consider all strings formed by rearranging the letters in s. After ordering these strings in dictionary order, return the middle term. (If the sequence has a even length n, define its middle term to be the (n/2)th term.)

Example

For s = "abc", the result should be "bac".

The permutations in order are:

"abc", "acb", "bac", "bca", "cab", "cba"

So, The middle term is "bac".

Input/Output

[input] string s

unique letters (2 <= length <= 26)

[output] a string

middle permutation.

	public static List<String> generater(String input) {
		List<String> reslut = new ArrayList<String>();
		MiddlePermutation.permutation("", input, reslut);
		return reslut;
	}

	private static void permutation(String chars, String input, List<String> result) {

		if (input.isEmpty()) {
			result.add(chars + input);
			return;
		}
		for (int i = 0; i < input.length(); i++) {
			permutation(chars + input.charAt(i), input.substring(0, i) + input.substring(i + 1), result);
		}
	}

	public static String findMidPerm(String strng) {
		// your code here!
		List<String> result =MiddlePermutation.generater(strng);
		Collections.sort(result);
		return result.get((result.size() / 2) - 1);
	}

	public static String findMidPerm(String strng) {
		// your code here!
		char [] temp = strng.toCharArray();
		Arrays.sort(temp);
		String sorted = new String(temp);
		
		if(sorted.length()%2==0) {
			int middle = sorted.length()/2-1;
			StringBuilder remainder = new StringBuilder(sorted.substring(0,middle)+sorted.substring(middle+1));
			return sorted.substring(middle,middle+1) + remainder.reverse().toString();
		}else {
			int middle = sorted.length()/2;
			String remainder = sorted.substring(0,middle)+sorted.substring(middle+1);
			return sorted.substring(middle,middle+1) + findMidPerm(remainder.toString());
		}
	}

# Josephus Permutation

This problem takes its name by arguably the most important event in the life of the ancient historian Josephus: according to his tale, he and his 40 soldiers were trapped in a cave by the Romans during a siege.

Refusing to surrender to the enemy, they instead opted for mass suicide, with a twist: they formed a circle and proceeded to kill one man every three, until one last man was left (and that it was supposed to kill himself to end the act).

Well, Josephus and another man were the last two and, as we now know every detail of the story, you may have correctly guessed that they didn't exactly follow through the original idea.

You are now to create a function that returns a Josephus permutation, taking as parameters the initial array/list of items to be permuted as if they were in a circle and counted out every k places until none remained.

Tips and notes: it helps to start counting from 1 up to n, instead of the usual range 0..n-1; k will always be >=1.

For example, with n=7 and k=3 josephus(7,3) should act this way.

[1,2,3,4,5,6,7] - initial sequence

[1,2,4,5,6,7] => 3 is counted out and goes into the result [3]

[1,2,4,5,7] => 6 is counted out and goes into the result [3,6]

[1,4,5,7] => 2 is counted out and goes into the result [3,6,2]

[1,4,5] => 7 is counted out and goes into the result [3,6,2,7]

[1,4] => 5 is counted out and goes into the result [3,6,2,7,5]

[4] => 1 is counted out and goes into the result [3,6,2,7,5,1]

[] => 4 is counted out and goes into the result [3,6,2,7,5,1,4]

So our final result is: josephus([1,2,3,4,5,6,7],3)==[3,6,2,7,5,1,4]

	public static <T> List<T> josephusPermutation(final List<T> items, final int k) {
		    int current = 0;
		    List<T> result= new ArrayList<T>();
		    while (items.size() > 0) {
		    	
		      current = (current-1+k)%items.size();
		      /*
  			  current+=k-1;
			  while(current > = items.size()) {
					current -= items.size();
			  }
			  */
		      result.add(items.remove(current));
		    }
		    return result;
	}