CODEWITHSUNDEEP
calgorithmdata-structurespermutationbacktracking
ss321c
ss321c

Reputation: 799

trying to understand permutation generation

I am trying to understand a permutation algorithm given here what I am not clear is with first block of pseudo code where they mention

array = [1, 2, 3, 4]
function permutation(start, end):
#i will go from start to end
    for i -> (start, end+1):
        permutation(start+1,end)

why has end+1 used in for i loop this is not clear to me as far as I understand end+1 should go out of index of array to which permutation has to be applied, but this is not the case here this is what I am not clear with.

Upvotes: 0

Views: 81

Answers (2)

ManishM
ManishM

Reputation: 593

for i -> (start, end+1)

It means iterate for every value beginning from start, with auto-increment and condition satisfying end+1

permutation(start+1,end)

It is just the same function call with parameters having values of start and end passed into it

e.g 

function permutation(start, end)

with start = 1 and end = 10

Inside foreach will iterate starting from 1 with auto-increment till it reaches 10, means less that (10+1) = 11

Then, permutation(start+1,end) is called Let's say for the first item start = 1. It will call with start as 2 and end as 10

Upvotes: 0

Antti Haapala -- Слава Україні
Antti Haapala -- Слава Україні

Reputation: 133879

The author is familiar in Python, and uses the same (unfortunate) idiom in the pseudo code. In Python, the start of a range is inclusive, while the end is exclusive. Later on that page the Python code excerpt proves that that indeed is the case:

for i in range(start, end+1):

With this code i will be sequentially assigned all integers from start to end inclusive, but excluding the end + 1.

In C one would often use < in loops - then it would happen there too:

for (size_t i = start; start < end + 1; start++)
                               ^^^^^^^

though more natural would be to write

for (size_t i = start; start <= end; start++)

Upvotes: 1

Related Questions