. Consider the problem of generating all the possible permutations of length n. For example, the permutations of length 3 are: {1,2,3}, {2,1,3},{2,3,1}, {1,3,2}, {3,1,2}, {3,2,1}.
Write a Well documented pseudocode of a non-recursive algorithm that computes all the permutations of size n. The only data structure allowed is a queue. Any other memory usage should be O(1). Calculate the time complexity of your algorithm using the big-Oh notation. Show all calculations.
(The code should be written in Java!!)
Pseudocode of a non-recursive algorithm:
Screenshots of the java Program: Generat_All_Permutations.java
Sample output:
Code to copy: Generat_All_Permutations.java
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class Generat_All_Permutations
{
/*function name: permutations
* parameters: n- size
* non-recursive algorithm that computes all
* the permutations of size n
*/
public static void findPermutations(int n)
{
String startStr = "";
//create inital string of length
n
for (int i = 1; i <= n;
i++)
{
startStr += "" +
i;
}
// Create a queue using to store
permutations
Queue<String> queue = new
LinkedList<>();
// Add first characeter of the
startStr into queue
queue.add(String.valueOf(startStr.charAt(0)));
// Add all the characters into
queue for permutations
for (int x = 1; x <
startStr.length(); x++)
{
/*consider
previously constructed partial permutation one by one
*iterate
backwards to avoid ConcurrentModificationException)
*/
for (int y =
queue.size() - 1; y >= 0; y--)
{
// remove current partial permutation from the
queue
String str = queue.remove();
/* Insert next character of the specified string
in all
* possible positions of current partial
permutation. Then
* insert each of these newly constructed string
in the list
*/
for (int k = 0; k <= str.length(); k++)
{
// Advice: use StringBuilder
for concatenation
String newS =
str.substring(0, k);
newS +=
startStr.charAt(x);
newS +=
str.substring(k);
//add new string into
queue
queue.add(newS);
}
}
}
//Print All permutations of the
string length n
while(!queue.isEmpty())
{
// remove current partial
permutation from the queue
String str =
queue.remove();
System.out.print("{");
for (int k = 0;
k < str.length(); k++)
{
if(k==str.length()-1)
System.out.print(str.charAt(k)+"} ");
else
System.out.print(str.charAt(k)+",");
}
}
}
/* program to generate all permutations of a
String
* using non-recursive
*/
public static void main(String[] args)
{
//Scanner object to read N
value
Scanner sc=new
Scanner(System.in);
//Prompt n value
System.out.print("Enter Length of
the starting String: ");
int n = sc.nextInt();//read n
value
System.out.println("\nAll
permutations: ");
//call method findPermutations to print all
permutations
findPermutations(n);
}
}
. Consider the problem of generating all the possible permutations of length n. For example, the...
Write an algorithm for generating all the permutations of(1,2,3,...,n) exactly once.
python code,please! Task 3:N ns Brute For In mathematics, the notion of permutation relates to the act of arranging all the members of a set into some sequence or order, or if the set is already ordered, rearranging (reordering) its elements, a process called permuting. The number of permutations on a set of n elements is given by n! (Read as n factorial). For example, there are 2!2 x 1- 2 permutations of 11,2), 2,1) and 3!-3x2x16 permutations of (1,2,3),...
Q2. Answer the following questions assignment, you will develop a well-documented pseudocode that generates all possible subsets of a given set T (i.e. power set of T) containing n elements with the following requirements: your solution must be non-recursive, and must use a stack and a queue to solve the problem. For example: ifT- {2, 4, 7,9; then your algorithm would generate: U, t2), (4;, {7), {9;, 12,4), 12,7;, 12.9;, 14,7), 14,9), 17,9;, ...etc. (Note: your algorithm's output need not...
PYTHON I need help with this Python problem, please follow all the rules! Please help! THANK YOU! Bonus Question Implement an efficient algorithm (Python code) for finding the 11th largest element in a list of size n. Assume that n will be greater than 11. det find 11th largest numberlissy Given, lissy, a list of n integers, the above function will return the 11th largest integer from lissy You can assume that length of lissy will be greater than 11....
JAVA 3 PLEASE ANSWER AS MANY QUESTIONS AS POSSIBLE! ONLY 2 QUESTIONS LEFT THIS MONTH!!! Question 12 pts Which is a valid constructor for Thread? Thread ( Runnable r, int priority ); Thread ( Runnable r, String name ); Thread ( int priority ); Thread ( Runnable r, ThreadGroup g ); Flag this Question Question 22 pts What method in the Thread class is responsible for pausing a thread for a specific amount of milliseconds? pause(). sleep(). hang(). kill(). Flag...