How to return all array permutations iteratively into a two-dimensional array?

I am trying to write a program that will iterate through all possible permutations of a String array, and return a two dimensional array with all the permutations. Specifically, I am trying to use a String array of length 4 to return a 2D array with 24 rows and 4 columns.

I have only found ways to print the Strings iteratively but not use them in an array. I have also found recursive ways of doing it, but they do not work, as I am using this code with others, and the recursive function is much more difficult.

For what I want the code to do, I know the header should be:

public class Permutation {      public String[][] arrayPermutation(String[] str)      {           //code to return 2D array      } } 

//I tried using a recursive method with heap’s algorithm, but it is very //complex with its parameters.

I am very new to programming and any help would be greatly appreciated.

Generate all permutations of 1 to n with i stacks

Assume we have i stacks. the possible actions are:

  1. push to first stack form input
  2. pop from stack i and push it to stack i+1
  3. pop from last stack to output

If we have numbers of 1 to n starting from 1 in the input, what is the minimum value of i which can generate all permutations of 1 to n at the output?

The options are:

  1. 1
  2. 2
  3. n-1
  4. n

Option 1 obviously is not the answer, and also it’s totally possible with n and n-1 stacks witch removes the option 4.

The real question is “is it possible doing it with 2 stacks or we need n-1” ?

Permutations covered by subgroups?

Given integer $ m\in[1,n]$ fix a set $ \mathcal T$ of permutations in $ S_n$ . There are subgroups $ G_1,\dots,G_m$ of $ S_n$ so that $ \mathcal T$ is covered by cosets of $ G_1,\dots,G_m$ .

  1. My problem then is given $ \mathcal T$ is there always an $ m=O(poly(n))$ such that there are elements $ g_1,\dots,g_m\in S_n$ and some subgroups of $ G_1,\dots,G_m$ of $ S_n$ such that

$ $ \mathcal T\subseteq\cup_{i=1}^mg_iG_i$ $ $ $ (\sum_{i=1}^m|G_i|-|\mathcal T|)^2<m’$ $ where both $ m$ and $ m’$ are $ O(poly(n))$ .

  1. If not what is the trade off between $ m$ and $ m’$ ?

  2. Is it possible to get at least $ O(subexp(n))$ for both?

  3. If $ m’=0$ is there always a minimum $ m$ for all $ \mathcal T$ ?

Python program to print all permutations of a string in lexicographic order using recursion

An assignment at school required me to print all permutations of a string in lexicographic or dictionary order.

Here is my solution to the task –

from math import factorial  def print_permutations_lexicographic_order(s):      seq = list(s)     for _ in range(factorial(len(seq))):         print(''.join(seq))         nxt = get_next_permutation(seq)         # if seq is the highest permutation         if nxt is None:             # then reverse it             seq.reverse()         else:             seq = nxt  def get_next_permutation(seq):     """     Return next greater lexicographic permutation. Return None if cannot.      This will return the next greater permutation of seq in lexicographic order. If seq is the highest permutation then this will return None.      seq is a list.     """     if len(seq) == 0:         return None      nxt = get_next_permutation(seq[1:])      # if seq[1:] is the highest permutation     if nxt is None:         # reverse seq[1:], so that seq[1:] now is in ascending order         seq[1:] = reversed(seq[1:])          # find q such that seq[q] is the smallest element in seq[1:] such that         # seq[q] > seq[0]         q = 1         while q < len(seq) and seq[0] > seq[q]:             q += 1          # if cannot find q, then seq is the highest permutation         if q == len(seq):             return None          # swap seq[0] and seq[q]         seq[0], seq[q] = seq[q], seq[0]          return seq     else:         return [seq[0]] + nxt   s = input('Enter the string: ') print_permutations_lexicographic_order(s)) 

Here are some example inputs/outputs:

Enter the string: cow >>> cow     cwo     ocw     owc     wco     woc  Enter the string: dogs >>> dogs     dosg     dsgo     dsog     gdos     gdso     gods     gosd     gsdo     gsod     odgs     odsg     ogds     ogsd     osdg     osgd     sdgo     sdog     sgdo     sgod     sodg     sogd     ogds     ogsd 

So, I would like to know whether I could make my program shorter and more efficient.

Any help would be highly appreciated.

Finding the sublist with best utility function among all list’s permutations

I try to find the the better solution in terms of time complexity. Among the list of elements I need to find the sublist with maximum value of given utility function.

Each element has it’s own type. The type of the adjusted element in the sublist should be different

My code works, I find it not optimal. I guess there is a room for improvement in terms time complexity.

import sys #python 3.5  class Object:     def __init__(self, initial_position, object_type):         self.initial_position = initial_position         self.object_type = object_type      @property     def object_relevance(self):         '''         object utility function         '''         return 2 ** (-self.initial_position)   class ObjectList:     def __init__(self, list):         self.object_list = list         self.rel = 0         self.best_list = []       def _list_relevance(self, object_sub_list):         '''         list utility function         '''         relevance = 0         for j in range(len(object_sub_list)):             relevance += (2 ** (-j)) * object_sub_list[j].object_relevance         return relevance       def _check_sub_list_permissibility(self, object_sub_list):         for i in range(len(object_sub_list) - 1):             if object_sub_list[i].object_type == object_sub_list[i + 1].object_type:                 return False             else:                 pass         return True       def _element_not_exist_in_the_list(self, object_sub_list, elem):         for object in object_sub_list:             if elem.initial_position == object.initial_position:                 return False         return True       def _traverse(self, object_list, init_list):         for elem in object_list:             try_list = init_list.copy()             if self._element_not_exist_in_the_list(try_list, elem):                 try_list.append(elem)                 if self._check_sub_list_permissibility(try_list):                     init_list = try_list                     if self._list_relevance(init_list) > self.rel:                         self.best_list = init_list                         self.rel = self._list_relevance(init_list)                     next = [object for object in object_list if object.initial_position != elem.initial_position]                     self._traverse(next, init_list)       def find_relevant_subset(self):         self._traverse(self.object_list, [])         return self.best_list  if __name__ == '__main__':     input = sys.stdin.read()     data = list(map(int, input.split()))     n, m = data[:2]     a_list = [Object(i,object_type) for i, object_type in enumerate(data[2:])]     object_list = ObjectList(a_list)     best_list = object_list.find_relevant_subset()     return_format = ' '.join([str(object.initial_position) for object in best_list])     sys.stdout.write(return_format) 

The input format: The first line contains numbers separated by a space n and m. m – is the number of unique types and n is the number of elements. In the next n lines of the input the type of every element is specified.

10 2 1 1 1 0 0 1 0 1 1 1 

So in the example above we have 10 elements with two different types (0 and 1). The input specifies the type of each element. Each object has it’s own type (in this example – 0 or 1) object_type and the order index initial_position.

The output format: 0 3 1 4 2 6 5

The goal is to find the sublist with maximum value of given utility function (_list_relevance).

This output shows the list of element’s initial_position. Also the object_type of the adjusted elements in this list are different.

  • The element with initial_position == 0 has object_type == 1
  • The element with initial_position == 3 has object_type == 0
  • The element with initial_position == 1 has object_type == 1
  • The element with initial_position == 4 has object_type == 0
  • The element with initial_position == 2 has object_type == 1
  • The element with initial_position == 6 has object_type == 0
  • The element with initial_position == 5 has object_type == 1

My algorithm: I tried to represent all possible combinations of the initial list as a tree and perform the DFS consider the given constrains. My code works, I find it not optimal. I guess there is a room for improvement in terms time complexity.

Projection on space of permutations of lower diagonal matrices

Let $ G$ be the group of all $ n\times n$ permutation matrices and let $ V$ be the vector space of all $ n$ -dimensional lower diagonal matrices. Then I define the set $ $ X = \{P\cdot L\cdot P^T \mid \forall P\in G, L\in V\}, $ $ where “$ \cdot$ ” is matrix multiplication. That is, $ X$ is the set of all lower diagonal matrices with possible rows and colums that are permuted at the same time.

I am interested in the orthogonal projection of a general matrix $ M\in\mathbb{R}^{n\times n}$ on the set $ X\subset \mathbb{R}^n$ . Does anyone know if there is a more efficient method to do it than projecting on each space $ $ V_P = \{P\cdot L\cdot P^T \mid \forall L\in V\} $ $ for every individual $ P\in G$ and then taking the shortest one?

Thank you in advance!

permutations cycle

I am doin abstract algebra problems, but unfortunately the book we are sing for the class is quite poor and leaves out lots of definitions and explainations, so I am not even sure if I completely understand the “rules of the game.” Only when I thought I started getting it, i realised that trying my generalization in partial cases I get wrong results; also wolfram alpha find another result. I am not sure whats write and whats wrong now.

Here is my problem and attempted solution:

(a) Find $ (1 \ 2 \dots n)(1 \ 2) (1 \ 2 \dots n)^{-1}$ . \end{problem}

\textbf{Solution.}

\begin{eqnarray*} \nonumber (1 \ 2 \dots n)(1 \ 2) (1 \ 2 \dots n)^{-1} &=&(1 \ 2 \ \dots n)(1 \ 2) (n \dots 2 \ 1) \ &=& (1 \ 3 \ 4 \ \dots [n-1] \ n)(1 \ 2)(1 \ 2) (n \dots 2 \ 1) \ &=& (1 \ 3 \ 4 \ \dots [n-1] \ n) (n \ [n-1]\dots 4 \ 3 \ 2 \ 1) \ &=& (1 \ 3){(3 \ 4) \dots ([n-1] \ n) (n \ [n-1])\dots (4 \ 3)}(3 \ 2)(2 \ 1) \ \text{[that nice chain-cancellation]}&=& (1 \ 3)\cancel{(3 \ 4)} \cancel{\dots} \cancel{([n-1] \ n)}\cancel{ (n \ [n-1])}\cancel{\dots}\cancel{ (4 \ 3)}(3 \ 2)(2 \ 1) \ &=& (1 \ 3)(3 \ 2)(2 \ 1) \ &=& (1 \ 2\ 3)(2 \ 1) \ &=& (1 \ 3)(1 \ 2)(2 \ 1) \ &=& (1 \ 3) \end{eqnarray*} \vspace{0.3cm}

(b) Find $ (1 \ 2 \dots n)^2(1 \ 2) (1 \ 2 \dots n)^{-2}$ .

\begin{eqnarray*} \nonumber (1 \ 2 \dots n)^2(1 \ 2) (1 \ 2 \dots n)^{-2} &=&(1 \ 2 \ \dots n)(1 \ 2 \ \dots n)(1 \ 2) (n \dots 2 \ 1)(n \dots 2 \ 1) \ \text{[substituting from part (a)]} &=&(1 \ 2 \ \dots n)\bigg[(1 \ 2 \ \dots n)(1 \ 2) (n \dots 2 \ 1)\bigg](n \dots 2 \ 1) \ &=& (1 \ 2 \ \dots n ) \bigg[(1 \ 3)\bigg] (n \dots 2 \ 1) \ &=& (1 \ 2 \ \dots n ) (1 \ 3) (n \dots 2 \ 1) \ &=& (1 \ 4 \ \dots n ) (1 \ 2 \ 3)(1 \ 3) (n \dots 2 \ 1) \ &=& (1 \ 4 \ \dots n ) ( 2 \ 3 \ 1)(1 \ 3) (n \dots 2 \ 1) \ &=& (1 \ 4 \ \dots n ) ( 2 \ 3)(3 \ 1)(1 \ 3) (n \dots 2 \ 1) \ &=& (1 \ 4 \ \dots n ) ( 2 \ 3) (n \dots 2 \ 1) \ \text{[since the these cycles are disjoint]}&=& ( 2 \ 3)(1 \ 4 \ \dots n ) (n \dots 2 \ 1) \ &=& ( 2 \ 3)(1 \ 4)(4 \ 5) \dots ([n-1] \ n ) (n \ [n-1]) \dots(5 \ 4)(4 \ 3)(3 \ 2)( 2 \ 1) \ \text{[again, chain-cancellation]}&=& ( 2 \ 3)(1 \ 4)\cancel{(4 \ 5)}\cancel{ \dots}\cancel{ ([n-1] \ n )}\cancel{ (n \ [n-1])}\cancel{ \dots}\cancel{(5 \ 4)}(4 \ 3)(3 \ 2)( 2 \ 1) \ &=& ( 2 \ 3)(1 \ 4)(4 \ 3)(3 \ 2)( 2 \ 1) \ &=& ( 2 \ 3)(1 \ 4)(4 \ 3 \ 2 \ 1) \ &=& ( 2 \ 3)(1 \ 4)(4 \ 1)(4 \ 3 \ 2 ) \ &=& ( 2 \ 3)(4 \ 3 \ 2 ) \ &=& ( 2 \ 3)( 3 \ 2 \ 4) \ &=& ( 2 \ 3)( 3 \ 2)(2 \ 4) \ &=& (2 \ 4) \ \end{eqnarray*}

\clearpage

(c) Explain how to obtain $ (k \ k+1)$ from $ (1 \ 2 \dots n)$ and $ (1 \ 2)$ , for $ 1 \leq k < n$ .

\textbf{Solution.}

(d) Find $ (1 \ 2 )(2 \ 3)(1 \ 2)$ .

\textbf{Solution.}

\vspace{0.3cm}

\begin{equation} \nonumber (1 \ 2)(2 \ 3)(1 \ 2) = (1 \ 2 \ 3)(1 \ 2) = (1 \ 3)(1 \ 2) (1 \ 2) = (1 \ 3) \end{equation}

(e) Explain how to obtain any two cycle $ (j \ j+1)$ in $ S_n$ .

\textbf{Solution.}

\clearpage

(f) Use parts (a) to (e) and Lemma 3.7.1 to prove Lemma 3.7.5.

\textbf{Solution.}

Lemma 3.7.1 is given below.

enter image description here

\textbf{Lemma 3.7.1.} For $ n>1$ , $ (1 \ 2)$ and $ (1 \ 2 \dots n)$ generate $ S_n$ .

\begin{proof} By induction.

As in Lemma 3.7.1, we first consider the base case, i.e. $ n = 2$ , then we have $ S_2$ , since the identity $ \epsilon = (1 \ 2) (1 \ 2) = (1 \ 2) (2 \ 1) = (1)$ and $ \epsilon = (1 \ 2 ) ( 1 \ 2 ) = (2 \ 1) (1 \ 2) = (2)$ .

Circular (bracelets) permutations with alike things(reflections are equivalent) using polya enumeration

Circular permutations of N objects of n1 are identical of one type, n2 are identical of another type and so on, such that n1+n2+n3+….. = N? A similar question exists but it doesn’t address the case where reflections are under the same equivalent class.$ $ \frac{1}{N}\sum_{d | N} \phi(d) p_d^{N/d}$ $ This is when reflections are not the same. How does the equation change under this new restriction.

Note: I couldn’t comment on that question due to my low reputation, so I made this question.

How many permutations are there at a given Cayley distance from the identity?

Permutations $ \sigma$ in the symmetric groups $ S_n$ can be characterized by their Cayley distance $ C_\sigma$ , being the minimal number of transpositions needed to convert $ \{1,2,3,\ldots n\}$ into $ \sigma$ . The sign of the permutation is $ (-1)^{C_\sigma}$ .

For example, when $ \sigma=\{2, 3, 4, 5, 1\}$ , one has $ C_\sigma=4$ and for $ \sigma=\{1, 2, 3, 5, 4\}$ one has $ C_\sigma=1$ . Of the $ 5!$ permutations in $ S_5$ there are, respectively, $ 1,10,35,50,24 $ with Cayley distance $ C_\sigma=0,1,2,3,4$ .

Question: What is the general formula that counts the number of permutations at a given Cayley distance?

This question was motivated by my attempt to check an integral formula in the unitary group.

Rank and frequency of permutations

(a) Let $ [n] = \{1,\dotsc,n\}$ , and let $ \pi:[n]\to [n]$ be a permutation. Define an $ n$ -by-$ n$ matrix $ A=A(\pi)$ as follows: $ A_{i,j}=1$ if $ j>i$ and $ \pi(j)>\pi(i)$ , or $ j<i$ and $ \pi(j)<\pi(i)$ ; $ A_{i,j}=0$ otherwise.

For $ \pi$ generic, we expect the rank of $ A(\pi)$ to be $ n$ or close to $ n$ . At the same time, the rank of $ A(\pi)$ can be $ 0$ : it is $ 0$ if (and only if) $ \pi$ is the reflection $ \pi(k) = n+1-k$ .

What sort of upper bound can one give on the number of permutations $ \pi$ such that the rank of $ A(\pi)$ is small (say, at most $ \delta n$ , where $ 0<\delta<1$ )?

(b) More generally (in a way), we may consider words $ w$ of length $ 2n$ containing exactly one instance each of $ x_i$ and $ x_i^{-1}$ for each $ 1\leq i\leq n$ . Define an $ n$ -by-$ n$ matrix $ A=A(w)$ as follows: $ A_{i,j}=1$ if exactly one of $ x_j$ , $ x_j^{-1}$ appears between $ x_i$ and $ x_i^{-1}$ (or between $ x_i^{-1}$ and $ x_i$ , if they are in that order); $ A_{i,j}=0$ otherwise.

The number of words $ w$ such that the rank of $ A(w)$ is $ 0$ is relatively small (roughly $ 8^n$ ): the rank of $ A(w)$ can be $ 0$ only if $ w$ reduces to the trivial word. (Here “relatively small” means “small compared to $ n!$ .)

What sort of upper bound can one give on the number of words $ w$ of the kind we are considering such that the rank of $ A(w)$ is small (say, at most $ \delta n$ , where $ 0<\delta<1$ )?