Что такое set perm recursive в программирование

Class Notes: Recursion, Part 1

Recursion technically means that some function calls itself. However, fundamentally, using recursion is more than that — it is a powerful way to think about problem solving.

In recursion, we divide a function into two possible cases: a base case, which returns the result for a known small value, and a recursive case, which computes a result by calling the same function on a smaller value. In other words: we solve the problem by assuming it’s already solved!

def recursiveFunction(): if (this is the base case): do something non-recursive else: do something recursive

# Problem: sum all of the numbers in a given list def listSum(L): # Base Case: the list is empty, so the sum is 0 if (len(L) == 0): return 0 else: # Recursive Case: assume we already know the sum of the entire list # after the first element. Add that sum to the first element. return L[0] + listSum(L[1:]) print(listSum([2,3,5,7,11])) # 28

# Problem: sum all of the numbers from lo to hi, inclusive def rangeSum(lo, hi): if (lo > hi): return 0 else: return lo + rangeSum(lo+1, hi) print(rangeSum(10,15)) # 75

# Problem: raise the number base to the given exponent def power(base, expt): # assume expt is non-negative integer if (expt == 0): return 1 else: return base * power(base, expt-1) print(power(2,5)) # 32

def power(base, expt): # This version allows for negative exponents # It still assumes that expt is an integer, however. if (expt == 0): return 1 elif (expt < 0): # new recursive case! return 1.0 / power(base, abs(expt)) else: return base * power(base, expt-1) print(power(2,5)) # 32 print(power(2,-5)) # 1/32 = 0.03125

def interleave(list1, list2): # Allow for different-length lists if (len(list1) == 0): return list2 elif (len(list2) == 0): # new base case! return list1 else: return [list1[0] , list2[0]] + interleave(list1[1:], list2[1:]) print(interleave([1,2],[3,4,5,6])) # [1,3,2,4,5,6]

Just as we can write infinite loops, we can also write infinite recursive functions, which result in stack overflow, producing a RecursionError.

def sumToN(n): if n == 0: return 0 else: return n + sumToN(n-1) print(sumToN(3)) # 6 (works!) print(sumToN(-3)) # RecursionError: maximum recursion depth exceeded.

Debugging recursive code can be tricky because we not only have to know which function we are in, but which specific call to that function (since it calls itself repeatedly)! We can make it easier by keeping track of the recursion depth using an optional parameter, then adjusting the output based on that depth.

def rangeSum(lo, hi, depth=0): print(» » * depth + «rangeSum(» + str(lo) + «, » + str(hi) + «)») if depth == 10: input(«Pause (press enter to continue)») if (lo > hi): result = 0 else: result = lo + rangeSum(lo + 1, hi, depth + 1) print(» » * depth + «—>», result) return result print(rangeSum(10, 30))

Sometimes we want to write a function with certain parameters, but it would be helpful to use different parameters in the recursive call. We can do this by writing a wrapper function around the core recursive function. The wrapper can set up the additional parameters on the way in, and it can also parse and perhaps modify the recursive result on the way out. The wrapper function itself is not recursive, but the function it calls is!

# This time with a wrapper function that tracks the sum so far. def rangeSum(lo, hi): return rangeSumHelper(lo, hi, 0) def rangeSumHelper(lo, hi, sumSoFar): if (lo > hi): return sumSoFar else: return rangeSumHelper(lo+1, hi, lo+sumSoFar) print(rangeSum(10,15)) # 75

1. Using default parameters in recursion
   As we just saw, we can use wrapper functions to effectively add parameters that we need for recursion but which are not included in the top-level call. Another approach to do the same basic thing is to use default values. For example, here is one way to write rangeSum recursively using default parameters:

# Now with a default value instead of a wrapper function def rangeSum(lo, hi, sumSoFar=0): if (lo > hi): return sumSoFar else: return rangeSum(lo+1, hi, lo+sumSoFar) print(rangeSum(10,15)) # 75

# This is a typical, clean way without wrapper functions or default values: def reverseList(L): if (L == [ ]): return [ ] else: return reverseList(L[1:]) + [L[0]] print(reverseList([2,3,4])) # [4, 3, 2] (it works!) print(reverseList([5,6,7])) # [7, 6, 5] (yup!)

And here it is again, using a default value in a similar way that we just did in rangeSum above:

# Warning: This is BROKEN because it uses a mutable default value def reverseList(L, reversedSoFar=[]): if (L == [ ]): return reversedSoFar else: reversedSoFar.insert(0, L[0]) return reverseList(L[1:], reversedSoFar) print(reverseList([2,3,4])) # [4, 3, 2] (it works the first time!) print(reverseList([5,6,7])) # [7, 6, 5, 4, 3, 2]

Do not mutate the default value

# Fix #1: just do not mutate it! def reverseList(L, reversedSoFar=[]): if (L == [ ]): return reversedSoFar else: # reversedSoFar.insert(0, L[0]) reversedSoFar = [L[0]] + reversedSoFar # this is nondestructive! return reverseList(L[1:], reversedSoFar) print(reverseList([2,3,4])) # [4, 3, 2] (it works!) print(reverseList([5,6,7])) # [7, 6, 5] (and it works again!)

# Fix #2: use None instead of [] and create a new list to start def reverseList(L, reversedSoFar=None): if (reversedSoFar == None): reversedSoFar = [ ] # this creates a new list each time! if (L == [ ]): return reversedSoFar else: reversedSoFar.insert(0, L[0]) return reverseList(L[1:], reversedSoFar) print(reverseList([2,3,4])) # [4, 3, 2] (it works!) print(reverseList([5,6,7])) # [7, 6, 5] (and it works again!)

# Fix #3: use a wrapper function instead of a default value def reverseList(L): return reverseListHelper(L, [ ]) def reverseListHelper(L, reversedSoFar): if (L == [ ]): return reversedSoFar else: reversedSoFar.insert(0, L[0]) return reverseListHelper(L[1:], reversedSoFar) print(reverseList([2,3,4])) # [4, 3, 2] (it works!) print(reverseList([5,6,7])) # [7, 6, 5] (and this also works again!)

Recursion is perhaps most powerful when we make multiple recursive calls in the recursive case. This often lets us solve problems that we cannot easily solve with loops. You can think of this approach as divide and conquer. In order to solve a problem, we break it into smaller parts, solve each of those, then combine the solutions to get the final answer.

# Technically we don’t need multiple recursive calls here, but it’s a nice simple example. # Sum the list by splitting it in half, then summing each half. def listSum(L): if (len(L) == 0): return 0 elif (len(L) == 1): return L[0] else: mid = len(L)//2 return listSum(L[:mid]) + listSum(L[mid:]) print(listSum([2,3,5,7,11])) # 28

# In the Fibonacci sequence, each element is the sum of the two # elements before it. This translates nicely into recursive code! def fib(n): if (n < 2): return 1 # note: fib(0) and fib(1) are both 1 else: return fib(n-1) + fib(n-2) print([fib(n) for n in range(15)])

First attempt (without Python):

# This is the plan to solve Towers of Hanoi (based on magic!) magically move(n-1, source, temp, target) move( 1, source, target, temp) magically move(n-1, temp, target, source)

def move(n, source, target, temp): move(n-1, source, temp, target) move( 1, source, target, temp) move(n-1, temp, target, source) move(2, 0, 1, 2) # Does not work — infinite recursion

def move(n, source, target, temp): if (n == 1): print((source, target), end=»») else: move(n-1, source, temp, target) move( 1, source, target, temp) move(n-1, temp, target, source) move(2, 0, 1, 2)

def move(n, source, target, temp): if (n == 1): print((source, target), end=»») else: move(n-1, source, temp, target) move( 1, source, target, temp) move(n-1, temp, target, source) def hanoi(n): print(«Solving Towers of Hanoi with n python-code»> def move(n, source, target, temp, depth=0): print((» » * 3 * depth), «move», n, «from», source, «to», target, «via», temp) if (n == 1): print((» » * 3 * depth), (source, target)) else: move(n-1, source, temp, target, depth+1) move( 1, source, target, temp, depth+1) move(n-1, temp, target, source, depth+1) def hanoi(n): print(«Solving Towers of Hanoi with n python-code»> def iterativeHanoi(n): def f(k): return (k%3) if (n%2==0) else (-k%3) return [(f(move & (move-1)), f((move|(move-1))+1)) for move in range(1,1

def merge(A, B): # beautiful, but impractical for large N if ((len(A) == 0) or (len(B) == 0)): return A+B else: if (A[0] < B[0]): return [A[0]] + merge(A[1:], B) else: return [B[0]] + merge(A, B[1:]) def merge(A, B): # iterative (ugh) and destructive (double ugh), but practical. C = [ ] i = j = 0 while ((i < len(A)) or (j < len(B))): if ((j == len(B)) or ((i < len(A)) and (A[i]

# In Quick Sort, select an element to pivot around, organize all elements to # the left and right of the pivot, then Quick Sort each side. def quickSort(L): if (len(L) < 2): return L else: first = L[0] # pivot rest = L[1:] lo = [x for x in rest if x < first] hi = [x for x in rest if x >= first] return quickSort(lo) + [first] + quickSort(hi) print(quickSort([1,5,3,4,2,0]))

def f(L): if L == [ ]: return 0 else: if (f(L[1:]) > 10): return 1 + f(L[1:]) else: return 2 + f(L[1:]) print(f(list(range(10)))) # prints 16 # However. uncomment the next line and run it: # print(f(list(range(30)))) # super, super slow!

def f(L): if L == [ ]: return 0 else: rest = f(L[1:]) # <-- this is the fix (recurse only once) if (rest >10): return 1 + rest else: return 2 + rest print(f(list(range(10)))) # 16 (whew) print(f(list(range(100)))) # 106, zippy quick. Problem solved!

—> We sometimes need to combine iteration and recursion while problem solving.

# Problem: given a list a, return a list with all the possible subsets of a. def powerset(a): # Base case: the only possible subset of an empty list is the empty list. if (len(a) == 0): return [ [] ] else: # Recursive Case: remove the first element, then find all subsets of the # remaining list. Then for each subset, use two versions of that subset: # one without the first element, and another one with it. partialSubsets = powerset(a[1:]) allSubsets = [ ] for subset in partialSubsets: allSubsets.append(subset) allSubsets.append([a[0]] + subset) return allSubsets print(powerset([1,2,3]))

# Problem: given a list a, find all possible permutations (orderings) of the # elements of a def permutations(a): # Base Case: the only permutation of an empty list is the empty list if (len(a) == 0): return [ [] ] else: # Recursive Case: remove the first element, then find all possible # permutations of the remaining elements. For each permutation, # insert a into every possible position in that permutation. partialPermutations = permutations(a[1:]) allPerms = [ ] for perm in partialPermutations: for i in range(len(perm) + 1): allPerms.append(perm[:i] + [ a[0] ] + perm[i:]) return allPerms print(permutations([1,2,3]))

# Alternative Approach: choose each element as the starting element of the # permutation, then find all possible permutations of the rest. def permutations(a): if (len(a) == 0): return [ [] ] else: allPerms = [ ] for i in range(len(a)): partialPermutations = permutations(a[:i] + a[i+1:]) for perm in partialPermutations: allPerms.append([ a[i] ] + perm) return allPerms print(permutations([1,2,3]))

factorial

def factorial(n): result = 1 for i in range(2, n + 1): result *= i return result print(factorial(5))
def factorial(n): if (n < 2): return 1 else: return n * factorial(n - 1) print(factorial(5))

reverse

def reverse(s): reverse = «» for ch in s: reverse = ch + reverse return reverse print(reverse(«abcd»))

def reverse(s): if (len(s) < 2): return s else: mid = len(s)//2 return reverse(s[mid:]) + reverse(s[:mid]) print(reverse("abcd"))

digitSum

def digitSum(n): if n < 0: n = abs(n) result = 0 while n >0: result += n % 10 n = n // 10 return result print(digitSum(-12345))

def digitSum(n): if (n < 0): return digitSum(abs(n)) elif (n < 10): return n else: return (n % 10) + digitSum(n // 10) print(digitSum(-12345))

gcd (optional)

def gcd(x, y): while (y > 0): (x, y) = (y, x % y) return x print(gcd(500, 420)) # 20
def gcd(x, y): if (y == 0): return x else: return gcd(y, x % y) print(gcd(500, 420)) # 20

Recursion	Iteration
Elegance
Performance
Debuggability

Of course, these are just general guidelines. For example, it is possible to use recursion with high performance, and it is certainly possible to use (or abuse) iteration with very low performance.

Conclusion (for now): Use iteration when practicable. Use recursion when required (for «naturally recursive problems»).

1. «Recursion»: See «Recursion».
2. Google search:Recursion
3. Recursion comic:http://xkcd.com/244/
4. Droste Effect: See the Wikipedia page and this Google image search
5. Fractals: See the Wikipedia page and this Google image search and this infinitely-zooming video
6. The Chicken and Egg Problem (mutual recursion)
7. Sourdough Recipe: First, start with some sourdough, then.
8. Books:Godel, Escher, Bach; Metamagical Themas;
9. Wikipedia page on Recursion: See here.

How to write a recursive function that with certain time complexity

that must have a time complexity of like : $O(n^2), O(n^3), O(n^7), O(n^2!), O(2^n), O(9^n)$. Can anyone give some idea on how to solve this kind of recursion questions.

22.2k 4 4 gold badges 50 50 silver badges 110 110 bronze badges
asked Aug 23, 2012 at 6:21
785 1 1 gold badge 8 8 silver badges 16 16 bronze badges

$\begingroup$ Are you sure the question doesn’t ask for running times of $\Omega(n^2)$, $\Omega(n^3)$, etc? Otherwise the answer is trivial, since the running time of a noop is in the order of any of these classes. $\endgroup$

Aug 23, 2012 at 7:19

$\begingroup$ What have you tried? really you couldn’t solve any of them? and really you don’t have any idea about any of them, show us your try, then we could help you. $\endgroup$

Aug 23, 2012 at 11:00

$\begingroup$ @SaeedAmiri from the fibonacci recursion, I was able to write a function with O(x^n) time complexity.But I have no idea how to write a recursive function with time complexity of like O(n^x),O(n2!) $\endgroup$

Aug 23, 2012 at 14:38

$\begingroup$ Are you sure the exercise asked for $O(…)$ and not $\Theta(…)$? Recommended reading: How does one know which notation of time complexity analysis to use? $\endgroup$

Aug 23, 2012 at 17:30

$\begingroup$ @null, I think you looking for $\Theta$ as Gilles said, your current question is so simple (and I’m wonder why others upvote it), also even you change it to $\Theta$, it’s better to clarify your question (I think you mean different recursive methods not unique). $\endgroup$

Aug 23, 2012 at 19:02

3 Answers 3

$\begingroup$

I will assume the person stating the problem actually meant $\Theta$ where you write $O$; otherwise the question is trivial as Juho points out. Realising this may very well have been the point of the problem (or an intended shortcut for the observant), though.

Here is one basic idea to create an algorithm with runtime $\Theta(f(n))$: find a set of objects $S$ with $|S| = \Theta(f(n))$ and recursively enumerate it. If done correctly, this gives you a runtime in $\Omega(f(n))$; if you don’t waste time, you get $\Theta(f(n))$.

Some hints for the concrete runtimes you want to achieve:

• Given a set $T$ of $n$ objects, $|T \times T| \in \Theta(n^2)$.
• Given a set $T$ of $n$ (distinguishable) objects, the set $\operatorname(T)$ of all permutations of these objects has size $n!$.
• The set $\^n$ contains $2^n$ words.

Note that all these (simple) facts should be known from basic algorithm analysis and formal languages (and maybe combinatorics). The exam question can be solved by generalising and combining them.

answered Aug 27, 2012 at 10:01
72k 28 28 gold badges 177 177 silver badges 385 385 bronze badges
$\begingroup$

The idea is quite simple. Write your function run and analyze its time complexity $r(n)$. Is it then so that you can find any nonnegative constant $c$ and input size $n_0$ such that from which $r(n_0) \leq cg(n_0)$, where $g(n)$ is any particular function you desire? This idea comes from the formal definition of Big Oh. It might be helpful to build up intuition by plotting something, see here.

Here’s a concrete implementation. It’s not very meaningful, but it doesn’t have to be.

void run(int n)

The function is recursive and clearly runs in constant time. It is easy to verify by for example plotting, that yes, at some point $n^2$ and $n^3$ start to dominate. Hence, the the time complexity of the implementation is in both $O(n^2)$ and $O(n^3)$. Similar reasoning holds for other functions.

answered Aug 23, 2012 at 8:47
22.5k 7 7 gold badges 61 61 silver badges 115 115 bronze badges

$\begingroup$ -1 Seems you misread the question, OP asked for recursive functions with given time complexity, your answer is just general description of big oh. $\endgroup$

Aug 23, 2012 at 10:52

$\begingroup$ @SaeedAmiri Why do you think it’s relevant whether the function is recursive or not? This could have easily been a exam question testing your understanding of the big Oh notation. Really, if you know what the notation means the answer is easy and obvious (or the question is misinterpreted as suggested by Peter in the comments). $\endgroup$

Aug 23, 2012 at 11:03

$\begingroup$ Thank you very much for reminding me to understand what does big oh mean, I’ll take your great advice. But I never said answer is hard (which is obvious from my comment for OP), I said your answer is not an answer to the question, and by your great comment, still I can’t see any direct link between your answer and OPs question. $\endgroup$

Aug 23, 2012 at 11:58

$\begingroup$ @SaeedAmiri Being precise and careful is not exaggerating. What is simple and clear to you, might not be that for someone else. It’s only my loss if I waste my time answering the question and later on the OP clarifies and the meaning of the question changes. Please don’t worry about that. $\endgroup$

Aug 23, 2012 at 18:06

$\begingroup$ @SaeedAmiri: Every function is recursive, even if only trivially so. Look at my set of recursive giraffes: $\varnothing$. $\endgroup$

Aug 26, 2012 at 1:43
$\begingroup$

When you are given a problem statement there will be an input.The given input has to be countable in some way. In order to get the answer or output you got to manipulate the input in some way are the other in programming. The question is ,how many operation are you going to do on your inputs . it depends on problem requirement .

For example : In an sorted array of n elements . 1)searching can be done by checking each and every element . 2)And using the mathematical property that array is sorted you apply a very old trick called binary search .which divedes our search space into half every time we check our trick. This reduces our search space so as reducing the operations. 

please read Master theorem to know how to evaluate complexity.

In the case 1 we have complexity in big oh notation as O(n) where n is the input . In the case 2 we have complexity in big oh notation as O(log(n)) where n is the input . 

For basic please refer Big Oh

Coming to the recursion , Suppose our problem be searching, let us consider the binary search .

int binary_search(int A[], int key, int imin, int imax) < // test if array is empty if (imax < imin): // set is empty, so return value showing not found return KEY_NOT_FOUND; else < // calculate midpoint to cut set in half int imid = midpoint(imin, imax); // three-way comparison if (A[imid] >key) // key is in lower subset return binary_search(A, key, imin, imid-1); else if (A[imid] < key) // key is in upper subset return binary_search(A, key, imid+1, imax); else // key has been found return imid; >> 

Firstly for searching an element say X in our input length N then we check middle element in an sorted array to see whether element to be searched(x) is greater or lesser .If it is greater we search the element from middle element(n/2) to last element N recursively .If element to be search(x) is smaller than middle we search from 1 to (n/2) ,as we know that element after middle element is bigger than middle(x

Complete Search with Recursion

Harder problems involving iterating through the entire solution space, including those that require generating subsets and permutations.

Language: All

Prerequisites

Table of Contents

Warning !

Although knowledge of recursion is not strictly necessary for Bronze, we think that it makes more sense to include this module as part of Bronze rather than Silver.

Apple Division
CSES — Easy

Focus Problem – try your best to solve this problem before continuing!

good explanation + code, no need to repeat

Solution — Apple Division

Since n ≤ 20 n \le 20 n ≤ 20 , we can solve this by trying all possible divisions of n n n apples into two sets and finding the one with the minimum difference in weights. Here are two ways to do this.

Generating Subsets Recursively

The first method would be to write a recursive function which searches over all possibilities.

At some index, we either add weight i \texttt_i weight i ​ to the first set or the second set, storing two sums sum 1 \texttt_1 sum 1 ​ and sum 2 \texttt_2 sum 2 ​ with the sum of values in each set.

Then, we return the difference between the two sums once we’ve reached the end of the array.

Copy
 
#include  
 
 using namespace std; 
 
 using ll = long long; 
 
 int n; 
 
vectorlong long> weights; 
 
ll recurse_apples(int index, ll sum1, ll sum2)  
 
 // We've added all apples- return the absolute difference 
 
 if (index == n)  return abs(sum1 - sum2); > 
 
Copy
 
import java.io.*; 
 
 import java.util.*; 
 
 public class AppleDivision  
 
 static int n; 
 
 static int[] weights; 
 
 public static void main(String[] args) throws Exception  
 
 Kattio io = new Kattio(); 
 
Copy
 
n = int(input()) 
 
weights = list(map(int, input().split())) 
 
 def recurse_apples(i: int, sum1: int, sum2: int) -> int: 
 
 # We've added all apples- return the absolute difference 
 
 if i == n: 
 
 return abs(sum2 - sum1) 
 
 # Try adding the current apple to either the first or second set 
 
Generating Subsets with Bitmasks

Warning !
You are not expected to know this for Bronze.
A bitmask is an integer whose binary representation is used to represent a subset. In the context of this problem, if the i i i 'th bit is equal to 1 1 1 in a particular bitmask, we say the i i i 'th apple is in s 1 s_1 s 1 ​ . If not, we'll say it's in s 2 s_2 s 2 ​ . We can iterate through all subsets s 1 s_1 s 1 ​ if we check all bitmasks ranging from 0 0 0 to 2 N − 1 2^N-1 2 N − 1 .
Let's do a quick demo with N = 3 N=3 N = 3 . These are the integers from 0 0 0 to 2 3 − 1 2^3-1 2 3 − 1 along with their binary representations and the corresponding elements included in s 1 s_1 s 1 ​ . As you can see, all possible subsets are accounted for.


Number
Binary
Apples In s 1 s_1 s 1 ​




0
000
 < >\ 


1
001
 < 0 >\ 


2
010
 < 1 >\ 


3
011
 < 0 , 1 >\ 


4
100
 < 2 >\ 


5
101
 < 0 , 2 >\ 


6
110
 < 1 , 2 >\ 


7
111
 < 0 , 1 , 2 >\

With this concept, we can implement our solution.
You'll notice that our code contains some fancy bitwise operations:
1 
The & (AND) operator will take two integers and return a new integer. a & b for integers a a a and b b b will return a new integer whose i i i th bit is turned on if and only if the i i i 'th bit is turned on for both a a a and b b b . Thus, mask & (1 
If you wanna learn more about them, we have a dedicated module for bitwise operations.
Copy
 
#include  
 
 using namespace std; 
 
 using ll = long long; 
 
 int main()  
 
 int n; 
 
 cin >> n; 
 
 vectorll> weights(n); 
 
 for (ll &w : weights)  cin >> w; > 
 
Copy
 
import java.io.*; 
 
 import java.util.*; 
 
 public class AppleDivision  
 
 public static void main(String[] args) throws Exception  
 
 Kattio io = new Kattio(); 
 
 int n = io.nextInt(); 
 
 int[] weights = new int[n]; 
 
 for (int i = 0; i  n; i++)  weights[i] = io.nextInt(); > 
 
Copy
 
n = int(input()) 
 
weights = list(map(int, input().split())) 
 
ans = float("inf") 
 
 for mask in range(1  n): 
 
 sum1 = 0 
 
 sum2 = 0 
 
 for i in range(n): 
 
 # Checks if the ith bit is set 
 
 if mask & (1  i): 
 
A permutation is a reordering of a list of elements.
Creating Strings I

CSES - Easy
Focus Problem – try your best to solve this problem before continuing!
This term is mentioned quite frequently, ex. in USACO Bronze - Photoshoot.
Think about how are words ordered in a dictionary. (In fact, this is where the term "lexicographical" comes from.)
In dictionaries, you will see that words beginning with the letter a appears at the very beginning, followed by words beginning with b , and so on. If two words have the same starting letter, the second letter is used to compare them; if both the first and second letters are the same, then use the third letter to compare them, and so on until we either reach a letter that is different, or we reach the end of some word (in this case, the shorter word goes first).
Permutations can be placed into lexicographical order in almost the same way. We first group permutations by their first element; if the first element of two permutations are equal, then we compare them by the second element; if the second element is also equal, then we compare by the third element, and so on.
For example, the permutations of 3 elements, in lexicographical order, are
[ 1 , 2 , 3 ] , [ 1 , 3 , 2 ] , [ 2 , 1 , 3 ] , [ 2 , 3 , 1 ] , [ 3 , 1 , 2 ] , [ 3 , 2 , 1 ] . [1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]. [ 1 , 2 , 3 ] , [ 1 , 3 , 2 ] , [ 2 , 1 , 3 ] , [ 2 , 3 , 1 ] , [ 3 , 1 , 2 ] , [ 3 , 2 , 1 ] .
Notice that the list starts with permutations beginning with 1 (just like a dictionary that starts with words beginning with a ), followed by those beginning with 2 and those beginning with 3. Within the same starting element, the second element is used to make comparisions.
Generally, unless you are specifically asked to find the lexicographically smallest/largest solution, you do not need to worry about whether permutations are being generated in lexicographical order. However, the idea of lexicographical order does appear quite often in programming contest problems, and in a variety of contexts, so it is strongly recommended that you familiarize yourself with its definition.
Some problems will ask for an ordering of elements that satisfies certain conditions. In these problems, if N ≤ 10 N \leq 10 N ≤ 10 , we can just iterate through all N ! = N ⋅ ( N − 1 ) ⋅ ( N − 2 ) ⋯ 1 N!=N\cdot (N-1)\cdot (N-2)\cdots 1 N ! = N ⋅ ( N − 1 ) ⋅ ( N − 2 ) ⋯ 1 permutations and check each permutation for validity.
Solution - Creating Strings I

What is the Python way for recursively setting file permissions?
What's the "python way" to recursively set the owner and group to files in a directory? I could just pass a 'chown -R' command to shell, but I feel like I'm missing something obvious. I'm mucking about with this:
 import os path = "/tmp/foo" for root, dirs, files in os.walk(path): for momo in dirs: os.chown(momo, 502, 20) 
This seems to work for setting the directory, but fails when applied to files. I suspect the files are not getting the whole path, so chown fails since it can't find the files. The error is: 'OSError: [Errno 2] No such file or directory: 'foo.html' What am I overlooking here?
17.6k 12 12 gold badges 64 64 silver badges 89 89 bronze badges

asked May 17, 2010 at 23:45

593 1 1 gold badge 5 5 silver badges 7 7 bronze badges
10 Answers 10
The dirs and files lists are all always relative to root - i.e., they are the basename() of the files/folders, i.e. they don't have a / in them (or \ on windows). You need to join the dirs/files to root to get their whole path if you want your code to work to infinite levels of recursion:
 import os path = "/tmp/foo" # Change permissions for the top-level folder os.chmod(path, 502, 20) for root, dirs, files in os.walk(path): # set perms on sub-directories for momo in dirs: os.chown(os.path.join(root, momo), 502, 20) # set perms on files for momo in files: os.chown(os.path.join(root, momo), 502, 20) 
Surprisingly, the shutil module doesn't have a function for this.
4,082 3 3 gold badges 41 41 silver badges 40 40 bronze badges

answered May 18, 2010 at 0:41

too much php too much php

89.1k 34 34 gold badges 129 129 silver badges 139 139 bronze badges
This has a bug which I just saw in my co-worker's code in production 🙂 The top level directory specified is not being chowned. I suggested an edit with a fix, hopefully it gets approved.
Mar 21, 2016 at 14:30
So my edit was rejected - good look to anyone who uses this and encounters the bug where /tmp/foo does NOT have its permissions changed. Good job moderating SO pythonians ������
Mar 21, 2016 at 16:53

@AvindraGoolcharan good catch - hopefully that was what you had in mind!

Apr 1, 2016 at 2:03

No need to loop through dirs since os.walk will go through all directories anyway. See my answer.

Aug 12, 2019 at 9:27
@AvindraGoolcharan Edits 1, 2, strike 3 you're out. Apparently 9 reviewers think adding os.chown(path, 502, 20) "deviates from intent", "should be a comment", or "is worth making a whole new answer for". Really. One line? Do all these people not know that chmod -R some_dir would change some_dir and all its child directories? I know you all are terrified about approving code edits, but still, this is silly
Feb 8, 2022 at 17:49
As correctly pointed out above, the accepted answer misses top-level files and directories. The other answers use os.walk then loop through dirnames and filenames . However, os.walk goes through dirnames anyway, so you can skip looping through dirnames and just chown the current directory ( dirpath ):
def recursive_chown(path, owner): for dirpath, dirnames, filenames in os.walk(path): shutil.chown(dirpath, owner) for filename in filenames: shutil.chown(os.path.join(dirpath, filename), owner) 
answered Aug 12, 2019 at 9:22

Christian Alis Christian Alis

6,636 5 5 gold badges 31 31 silver badges 30 30 bronze badges

Why shutil.chown instead of os.chown?

Mar 12, 2021 at 11:21
@gerardw I believe os.chown() only takes numeric uid and gid, whereas shutil.chown() will accept names or numeric IDs.
Mar 24, 2021 at 15:30

I could just pass a 'chown -R' command to shell

This is the simplest way, and gets lost in the question a bit, so just for clarity, you can do this in one line if you don't care about Windows:
os.system('chown -R 502 /tmp/foo') 
answered Aug 14, 2019 at 18:30

8,577 6 6 gold badges 54 54 silver badges 53 53 bronze badges
This doesn't get enough credit. It would be nice for shutil to gain the recursive functionality, but until then, why bother..
May 9 at 1:10
import os path = "/tmp/foo" for root, dirs, files in os.walk(path): for momo in dirs: os.chown(momo, 502, 20) for file in files: fname = os.path.join(root, file) os.chown(fname, aaa, bb) 
substitute aaa and bb as you please
answered May 18, 2010 at 0:25

41k 23 23 gold badges 87 87 silver badges 136 136 bronze badges

As in the accepted comment, /tmp/foo will NOT have the owner properly set. See my comments above.

Mar 21, 2016 at 14:34
try os.path.join(root,momo) that will give you full path
answered May 18, 2010 at 0:07

19.4k 16 16 gold badges 72 72 silver badges 103 103 bronze badges
Here is a function i wrote that uses glob to recursively list files and change their permissions.
import os import glob def recursive_file_permissions(path,mode,uid=-1,gid=-1): ''' Recursively updates file permissions on a given path. UID and GID default to -1, and mode is required ''' for item in glob.glob(path+'/*'): if os.path.isdir(item): recursive_file_permissions(os.path.join(path,item),mode,uid,gid) else: try: os.chown(os.path.join(path,item),uid,gid) os.chmod(os.path.join(path,item),mode) except: print('File permissions on not updated due to error.'.format(os.path.join(path,item))) 
it's not perfect, but got me where I needed to be
answered Jun 30, 2011 at 20:04

Keith Hamilton Keith Hamilton

21 1 1 bronze badge
The accepted answer misses top level files. This is the actual equivalent of chown -R .
import os path = "/tmp/foo" os.chown(path, 502, 20) for dirpath, dirnames, filenames in os.walk(path): for dname in dirnames: os.chown(os.path.join(dirpath, dname), 502, 20) for fname in filenames: os.chown(os.path.join(dirpath, fname), 502, 20) 
answered Sep 21, 2018 at 17:29

381 3 3 silver badges 9 9 bronze badges
No need to loop through dirnames since os.walk will go through all directories anyway. See my answer.
Aug 12, 2019 at 9:26
Don't forget the for f in files loop, either. Similarly, remember to os.path.join(root, f) to get the full path.
answered May 18, 2010 at 0:19

dash-tom-bang dash-tom-bang

17.5k 5 5 gold badges 46 46 silver badges 63 63 bronze badges
""" Requires python 3 Accepts name or id Usage: chown.py -p /temp/folder -u user -g group -r true or chown.py -p /temp/folder -u uid -g gid -r 1 user, group, and recursive are optional But must supply at least one of user or group Example: sudo chown.py -p /temp/filename -u some_user """ import argparse, os, sys from shutil import chown user = group = recursive = '' parser=argparse.ArgumentParser() parser.add_argument('-p', '--path') # help='file/path' parser.add_argument('-u', '--user') # , help='user' parser.add_argument( '-g','--group') # , help='group' parser.add_argument('-r', '--recursive', help=1) # , help='recursive' args=parser.parse_args() path = args.path if not path: raise Exception('missing path') if args.user: user = args.user if args.group: user = args.group if args.recursive: recursive = True if not user and not group: raise Exception('must supply user, group, or both') def change_owner(path, user='', group='') if user and not group: chown(path, user=user) elif not user and group: chown(path, group=group) else: chown(path, user, group) change_owner(path, user, group) if recursive: for dirpath, dirnames, filenames in os.walk(path): for dname in dirnames: change_owner(os.path.join(dirpath, dname), user, group) for fname in filenames: change_owner(os.path.join(dirpath, fname), user, group)