Writing your first Django application is a 4 part series available as part of the Django documentation at the following location http://docs.djangoproject.com/en/dev/intro/tutorial01/.
I have downloaded all the 4 parts and consolidated them as a single pdf document for easy reference. You may download the pdf here.
Feb 2, 2010
HTML & CSS for the design challenged
In this blog post I will talk about how developers who are design challenged can improve their html and css authoring skills. I have been doing back end coding for a long long time. My UI design skill was very much limited to designing console based applications & they were completely devoid of any kind of html and/or css design. However, I knew little html back then especially some of the header, paragraph & form tags but I have rarely used them. Therefore, I decided to formally learn them. My notion of formal learning is mostly self learning from books & then solving some of the interesting exercise problems. I will explain in little more detail on what are some of the important concepts a newbie to web design should be aware of when learning html & css. Please check the recommended reading section for information on books that I used for learning html & css.
HTML - Hyper Text Markup Language
- HTML is NOT for styling
- One of the key points to keep in mind about html is the fact that it is just a markup for the content. In other words, it just provides context to the content & nothing more. More importantly html should never be used to change the appearance of the content. You will basically markup the headers, paragraphs and any other contents of interest using html & that is all. CSS on the other hand does the job of changing the content appearance. This is kind of confusing to grasp initially because HTML does have some obsolete attributes to change the style or appearance of the content as well. Also, browsers add to the confusion by automatically styling the content using its own default styles (when no CSS is provided) thereby giving the notion that HTML does content styling as well.
- Block Vs Inline
- The next key point in understanding html is the concept of inline vs block elements. Elements like paragraphs <p> and headers <h1..h6> are block level elements. These elements start off on a new line & have some space above & below them whereas elements like <em>, <strong> etc are all inline elements & they stay with the line of text. This knowledge is required to better understand CSS.
- HTML Forms - GET Vs Post
- HTML forms enable sites to collect information from users & submit them to server for processing. All registrations that you come across on web sites are all examples of html forms. Form information is sent to a web server for processing when the user hits the submit form button. Users coding the form will have defined very clearly what module within the web server will be processing the form information. There are two modes for sending form information to server that you can specify while authoring the form. One is the 'GET' method and the other one is the 'POST' method. 'GET' appends the form element data to the URL that loads the form processing module. On the other hand, 'POST' sends a separate http request with the form element data to the server for processing. In both cases, data is sent in clear text & is therefore not a recommended approach for transmitting sensitive information like passwords. You should use secure sockets (https) for sending sensitive information.
- Browser modes - Standard vs. Quirks
- All browsers support two types of HTML rendering modes. One is the quirks mode which is out there basically to support pages authored using older versions of HTML. Browsers will attempt to render old pages authored using non-standard html as best as it can under quirks mode. If you would like to author your HTML pages using the new version you should configure your page to use the standards mode. You do this by defining a DOCTYPE element at the top of your html page using the STRICT tag. However, be warned, there are still people using older version of browsers that does not understand any of the enhancements in the new version. Please refer to the sidebar DOCTYPE Declaration for the syntax & the W3C site for more information.
- HTML authoring tools
- I use Notepad++ for authoring html documents but there are other commercial WYSIWYG authoring tools.
CSS - Cascading Style Sheets
- Box Model
- Every html element is rendered as a box by the browser. Therefore, it is imperative to understand what each box constitutes. For instance, browser renders the following <h1>text</h1> element as a box with the content "text" surrounded by some padding space followed by border and then some margin. However, the default rendering by the browser does not display any border and padding but just the content and margin. Please refer to the sidebar CSS Box Model for more information.
- Div Vs Span
- Div and Span are html elements. They are generic elements that you could customize to fit your needs. If none of the standard html elements defines your content best, you may go with the div and span elements and give them a name of your own. Div is a block level element whereas span is inline. Div element has completely replaced table element for page layouts. Usage of table elements for page layout is old school, cumbersome and not maintenance friendly. Therefore, it is good to have a solid understanding of div & its usage to best author CSS.
- Classes Vs IDs
- You can group related styles together as classes or IDs. You may then refer to these class names or IDs in the HTML document. Please note that you can only reference an ID once where as you can reference a class multiple times in your document.
- Floats
- Floats are key when it comes to laying out the elements on a page. When a html element is floated either to the left or right, all the elements beneath it will move up to occupy the empty space. Say, you have a note section marked up using the div element followed by a paragraph of text. You can float the div element to the right & the paragraph below it will occupy the empty space left of the note section & the space below it. Floated element acts like an island and all the elements underneath it will surround it like a stream of water. I picked up this analogy from some book/web site & I don't recall the name or address of the source.
- Graphics
- Basic understanding of image creation & manipulation techniques is required for creating decent layouts and styles in CSS. Experience with a simple paint program may not be adequate. However, at the same time you do not need to have extensive experience with advanced image manipulation software's like Adobe photoshop. You will need to know at the least to create basic solid colored background images and then add transparency or gradients to them as needed. GIMP is free open source tool that lets you do anything from basics like paint to advanced like photoshop.
- Tools
- Again, all you need is a notepad for creating CSS documents. Apart from that you may also need the firebug and/or the web developer extensions for firefox. These extensions provide an easy way to validate your CSS and HTML for any errors & will also let you review the styles for any existing web pages.
- General Design Tips
- Providing sufficient padding & margin improves the design a lot.
- Always use an appropriate font with suitable size for the body text. It is customary to have a sans-serif font for title and a serif one for body text but again it is a matter of choice.
- Always choose colors that are pleasing to the eye. One option would be to choose colors that do not contrast too much.
Oct 13, 2009
SICP Exercise Solutions - Chapter 2
Exercise 2.2. Consider the problem of representing line segments in a plane. Each segment is represented as a pair of points: a starting point and an ending point. Define a constructor make-segment and selectors start-segment and end-segment that define the representation of segments in terms of points. Furthermore, a point can be represented as a pair of numbers: the x coordinate and the y coordinate. Accordingly, specify a constructor make-point and selectors x-point and y-point that define this representation. Finally, using your selectors and constructors, define a procedure midpoint-segment that takes a line segment as argument and returns its midpoint (the point whose coordinates are the average of the coordinates of the endpoints). To try your procedures, you'll need a way to print points:
Solution:
b. Using your selectors, define a procedure total-weight that returns the total weight of a mobile.
d. Suppose we change the representation of mobiles so that the constructors are
Solution:
a)
Solution:
(define (make-point x y)
(cons x y))
(define (x-point p)
(car p))
(define (y-point p)
(cdr p))
(define (make-segment p1 p2)
(cons p1 p2))
(define (start-segment s)
(car s))
(define (end-segment s)
(cdr s))
(define (midpoint-segment ls)
(make-point
(avg (x-point (start-segment ls)) (x-point (end-segment ls)))
(avg (y-point (start-segment ls)) (y-point (end-segment ls)))
))
(define (avg x y)
(/ (+ x y) 2))
;Test Data
(define p1 (make-point 4 6))
(define p2 (make-point 8 18))
(define ls (make-segment p1 p2))
(midpoint-segment ls)
;6 12Exercise 2.27. Modify your reverse procedure of exercise 2.18 to produce a deep-reverse procedure that takes a list as argument and returns as its value the list with its elements reversed and with all sublists deep-reversed as well. For example, (define x (list (list 1 2) (list 3 4))) x ((1 2) (3 4)) (reverse x) ((3 4) (1 2)) (deep-reverse x) ((4 3) (2 1))Solution:
(define (rev items)
(define (helper items rl)
(if (null? items) rl
(helper (cdr items) (cons (car items) rl))))
(helper items null))
(define (deep-rev items)
(define (helper ritems)
(if (null? ritems)
null
(cons (if (not (pair? (car ritems))) (car ritems)(rev(car ritems))) (helper (cdr ritems)))))
(helper (rev items)))
Exercise 2.28. Write a procedure fringe that takes as argument a tree (represented as a list) and returns a list whose elements are all the leaves of the tree arranged in left-to-right order. For example,(define x (list (list 1 2) (list 3 4))) (fringe x) (1 2 3 4) (fringe (list x x)) (1 2 3 4 1 2 3 4)Solution:
(define (fringe items)
(cond ((null? items) null)
(else (append (if (not (pair? (car items))) (list (car items)) (car items)) (fringe (cdr items))))))
(define (deep-fringe items)
(if (not (exists-pair? items))
items
(deep-fringe (fringe items))))
(define (exists-pair? items)
(cond ((null? items) #f)
((pair? (car items)) #t)
(else (exists-pair? (cdr items)))))
Exercise 2.29. A binary mobile consists of two branches, a left branch and a right branch. Each branch is a rod of a certain length, from which hangs either a weight or another binary mobile. We can represent a binary mobile using compound data by constructing it from two branches (for example, using list):(define (make-mobile left right) (list left right))A branch is constructed from a length (which must be a number) together with a structure, which may be either a number (representing a simple weight) or another mobile:
(define (make-branch length structure) (list length structure))a. Write the corresponding selectors left-branch and right-branch, which return the branches of a mobile, and branch-length and branch-structure, which return the components of a branch.
b. Using your selectors, define a procedure total-weight that returns the total weight of a mobile.
d. Suppose we change the representation of mobiles so that the constructors are
(define (make-mobile left right) (cons left right)) (define (make-branch length structure) (cons length structure))How much do you need to change your programs to convert to the new representation?
Solution:
a)
(define (make-branch len st) (list len st)) (define (make-mobile lb rb) (list lb rb)) (define (left-branch m) (car m)) (define (right-branch m) (car (cdr m))) (define (branch-length b) (car b)) (define (branch-structure b) (car (cdr b)))b)
(define (mobile? m)
(pair? m))
(define (total-weight m)
(cond ((null? m) 0)
((not (mobile? m)) m)
(else (+ (total-weight (branch-structure (left-branch m)))
(total-weight (branch-structure (right-branch m)))))))
;Test
(define lb3 (make-branch 2 1))
(define rb3 (make-branch 1 2))
(define mb3 (make-mobile lb3 rb3))
(define lb2 (make-branch 3 mb3))
(define rb2 (make-branch 9 1))
(define mb2 (make-mobile lb2 rb2))
(define lb1 (make-branch 4 mb2))
(define rb1 (make-branch 8 2))
(define mb1 (make-mobile lb1 rb1))
(total-weight mb3)
(total-weight mb2)
(total-weight mb1)
d)(define (make-branch len st) (cons len st)) (define (make-mobile lb rb) (cons lb rb)) (define (left-branch m) (car m)) (define (right-branch m) (cdr m)) (define (branch-length b) (car b)) (define (branch-structure b) (cdr b))
Oct 3, 2009
SICP Exercise Solutions - Chapter 1
I have started learning SICP since I have been bitten by the functional programming bug. Therefore, I will be adding most of the solutions to SICP exercise problems in this blog. I am using Dr.Scheme to implement these solutions.
Exercise 1.3. Define a procedure that takes three numbers as arguments and returns the sum of the squares of the two larger numbers.
Solution:
(define (sos2ln a b c)(if (> a b)(if (> b c)(+ (sqr a) (sqr b))(+ (sqr a) (sqr c)))(if (> a c)(+ (sqr b) (sqr a))(+ (sqr b) (sqr c)))))
Exercise 1.11. A function f is defined by the rule that f(n) = n if n<3 and f(n) = f(n - 1) + 2f(n - 2) + 3f(n - 3) if n> 3. Write a procedure that computes f by means of a recursive process. Write a procedure that computes f by means of an iterative process.
Solution:
Recursive Process:
The numbers at the edge of the triangle are all 1, and each number inside the triangle is the sum of the two numbers above it. Write a procedure that computes elements of Pascal's triangle by means of a recursive process.
Solution:
Exercise 1.17. The exponentiation algorithms in this section are based on performing exponentiation by means of repeated multiplication. In a similar way, one can perform integer multiplication by means of repeated addition. The following multiplication procedure (in which it is assumed that our language can only add, not multiply) is analogous to the expt procedure:
Solution:
Exercise 1.29. Simpson's Rule is a more accurate method of numerical integration than the method illustrated above. Using Simpson's Rule, the integral of a function f between a and b is approximated as
h/3[y0+4y1+2y2+4y3+2y4+...+2yn-2+4yn-1+yn]
where h = (b - a)/n, for some even integer n, and yk = f(a + kh). (Increasing n increases the accuracy of the approximation.) Define a procedure that takes as arguments f, a, b, and n and returns the value of the integral, computed using Simpson's Rule. Use your procedure to integrate cube between 0 and 1 (with n = 100 and n = 1000), and compare the results to those of the integral procedure shown above.
Solution:
Exercise 1.32. a. Show that sum and product (exercise 1.31) are both special cases of a still more general notion called accumulate that combines a collection of terms, using some general accumulation function:
(accumulate combiner null-value term a next b)
Accumulate takes as arguments the same term and range specifications as sum and product, together with a combiner procedure (of two arguments) that specifies how the current term is to be combined with the accumulation of the preceding terms and a null-value that specifies what base value to use when the terms run out. Write accumulate and show how sum and product can both be defined as simple calls to accumulate.
Solution:
Exercise 1.33. You can obtain an even more general version of accumulate (exercise 1.32) by introducing the notion of a filter on the terms to be combined. That is, combine only those terms derived from values in the range that satisfy a specified condition. The resulting filtered-accumulate abstraction takes the same arguments as accumulate, together with an additional predicate of one argument that specifies the filter. Write filtered-accumulate as a procedure.
Solution:
Show how to express the following using filtered-accumulate:
a. the sum of the squares of the prime numbers in the interval a to b (assuming that you have a prime? predicate already written)
Solution:
Exercise 1.37. a. An infinite continued fraction is an expression of the form
As an example, one can show that the infinite continued fraction expansion with the Ni and the Di all equal to 1 produces 1/, where is the golden ratio (described in section 1.2.2). One way to approximate an infinite continued fraction is to truncate the expansion after a given number of terms. Such a truncation -- a so-called k-term finite continued fraction -- has the form
Suppose that n and d are procedures of one argument (the term index i) that return the Ni and Di of the terms of the continued fraction. Define a procedure cont-frac such that evaluating (cont-frac n d k) computes the value of the k-term finite continued fraction. Check your procedure by approximating 1/ using
(cont-frac
(lambda (i) 1.0)
(lambda (i) 1.0)
k)
for successive values of k. How large must you make k in order to get an approximation that is accurate to 4 decimal places?
b. If your cont-frac procedure generates a recursive process, write one that generates an iterative process. If it generates an iterative process, write one that generates a recursive process.
Solution:
Exercise 1.38. In 1737, the Swiss mathematician Leonhard Euler published a memoir De Fractionibus Continuis, which included a continued fraction expansion for e - 2, where e is the base of the natural logarithms. In this fraction, the Ni are all 1, and the Di are successively 1, 2, 1, 1, 4, 1, 1, 6, 1, 1, 8, .... Write a program that uses your cont-frac procedure from exercise 1.37 to approximate e, based on Euler's expansion.
Solution:
Exercise 1.3. Define a procedure that takes three numbers as arguments and returns the sum of the squares of the two larger numbers.
Solution:
(define (sos2ln a b c)(if (> a b)(if (> b c)(+ (sqr a) (sqr b))(+ (sqr a) (sqr c)))(if (> a c)(+ (sqr b) (sqr a))(+ (sqr b) (sqr c)))))
Exercise 1.11. A function f is defined by the rule that f(n) = n if n<3 and f(n) = f(n - 1) + 2f(n - 2) + 3f(n - 3) if n> 3. Write a procedure that computes f by means of a recursive process. Write a procedure that computes f by means of an iterative process.
Solution:
Recursive Process:
(define (f n)
(if (< n 3) n
(+ (f (- n 1)) (* 2 (f (- n 2))) (* 3 (f (- n 3))))))
Iterative Process: (define (f n)
(f-iter 2 1 0 n))
(define (f-iter a b c n)
(if (= n 0) c
(f-iter (+ a (* 2 b) (* 3 c)) a b (- n 1))))
Exercise 1.12. The following pattern of numbers is called Pascal's triangle.The numbers at the edge of the triangle are all 1, and each number inside the triangle is the sum of the two numbers above it. Write a procedure that computes elements of Pascal's triangle by means of a recursive process.
Solution:
(define (pt r c)
(cond ((or (< r 0) (< c 0)) 0)
((and (= r 1) (= c 1)) 1)
(else (+ (pt (- r 1)(- c 1))(pt (- r 1)c)))))Exercise 1.17. The exponentiation algorithms in this section are based on performing exponentiation by means of repeated multiplication. In a similar way, one can perform integer multiplication by means of repeated addition. The following multiplication procedure (in which it is assumed that our language can only add, not multiply) is analogous to the expt procedure:
(define (* a b)
(if (= b 0)
0
(+ a (* a (- b 1)))))
This algorithm takes a number of steps that is linear in b. Now suppose we include, together with addition, operations double, which doubles an integer, and halve, which divides an (even) integer by 2. Using these, design a multiplication procedure analogous to fast-expt that uses a logarithmic number of steps.Solution:
(define (even? x)
(= (remainder x 2) 0))
(define (dbl x)
(+ x x))
(define (half x)
(/ x 2))
(define (* a b)
(cond ((= b 0) 0)
((even? b) (* (dbl a) (half b)))
(else (+ a (* a (- b 1))))))Exercise 1.29. Simpson's Rule is a more accurate method of numerical integration than the method illustrated above. Using Simpson's Rule, the integral of a function f between a and b is approximated as
h/3[y0+4y1+2y2+4y3+2y4+...+2yn-2+4yn-1+yn]
where h = (b - a)/n, for some even integer n, and yk = f(a + kh). (Increasing n increases the accuracy of the approximation.) Define a procedure that takes as arguments f, a, b, and n and returns the value of the integral, computed using Simpson's Rule. Use your procedure to integrate cube between 0 and 1 (with n = 100 and n = 1000), and compare the results to those of the integral procedure shown above.
Solution:
(define (gs term a next b)
(if (> a b) 0
(+ (term a) (gs term (next a) next b))))
(define (sr f a b n)
(define h (/ (- b a) n))
(define (inc-2h x) (+ x (* 2 h)))
(* (/ h 3) (+ (f a) (* 2 (gs f (+ a (* 2 h)) inc-2h b)) (* 4 (gs f (+ a (* 1 h)) inc-2h b) (f (+ a (* n h)))))))Exercise 1.32. a. Show that sum and product (exercise 1.31) are both special cases of a still more general notion called accumulate that combines a collection of terms, using some general accumulation function:
(accumulate combiner null-value term a next b)
Accumulate takes as arguments the same term and range specifications as sum and product, together with a combiner procedure (of two arguments) that specifies how the current term is to be combined with the accumulation of the preceding terms and a null-value that specifies what base value to use when the terms run out. Write accumulate and show how sum and product can both be defined as simple calls to accumulate.
Solution:
(define (accumulate combiner null-value term a next b)
(if (> a b) null-value
(combiner (term a) (accumulate combiner null-value term (next a) next b))))
(define (sum-combiner x y)(+ x y))
(define (prod-combiner x y) (* x y))
(define (id x) x)
(define (inc x) (+ x 1))
(accumulate sum-combiner 0 id 1 inc 10)
;55
(accumulate prod-combiner 1 id 1 inc 5)
;120Exercise 1.33. You can obtain an even more general version of accumulate (exercise 1.32) by introducing the notion of a filter on the terms to be combined. That is, combine only those terms derived from values in the range that satisfy a specified condition. The resulting filtered-accumulate abstraction takes the same arguments as accumulate, together with an additional predicate of one argument that specifies the filter. Write filtered-accumulate as a procedure.
Solution:
(define (filtered-accumulate predicate combiner null-value term a next b)
(if (> a b) null-value
(combiner (if (predicate a) (term a) null-value) (filtered-accumulate predicate combiner null-value term (next a) next b))))Show how to express the following using filtered-accumulate:
a. the sum of the squares of the prime numbers in the interval a to b (assuming that you have a prime? predicate already written)
Solution:
(filtered-accumulate prime? sum-combiner 0 sqr 1 inc 3)
Exercise 1.37. a. An infinite continued fraction is an expression of the form
As an example, one can show that the infinite continued fraction expansion with the Ni and the Di all equal to 1 produces 1/, where is the golden ratio (described in section 1.2.2). One way to approximate an infinite continued fraction is to truncate the expansion after a given number of terms. Such a truncation -- a so-called k-term finite continued fraction -- has the form
Suppose that n and d are procedures of one argument (the term index i) that return the Ni and Di of the terms of the continued fraction. Define a procedure cont-frac such that evaluating (cont-frac n d k) computes the value of the k-term finite continued fraction. Check your procedure by approximating 1/ using
(cont-frac
(lambda (i) 1.0)
(lambda (i) 1.0)
k)
for successive values of k. How large must you make k in order to get an approximation that is accurate to 4 decimal places?
b. If your cont-frac procedure generates a recursive process, write one that generates an iterative process. If it generates an iterative process, write one that generates a recursive process.
Solution:
Recursive:
(define (cont-frac n d k)
(define (cont-frac-helper i)
(if (> i k) 0
(/ (n i) (+ (d i) (cont-frac-helper (+ i 1))))))
(cont-frac-helper 1)
)
Iterative:
(define (cont-frac-iter n d k)
(define (cont-frac-helper pd k)
(if (= k 0) pd
(cont-frac-helper (/ (n k) (+ (d k) pd)) (- k 1))))
(cont-frac-helper 0 k)
)Exercise 1.38. In 1737, the Swiss mathematician Leonhard Euler published a memoir De Fractionibus Continuis, which included a continued fraction expansion for e - 2, where e is the base of the natural logarithms. In this fraction, the Ni are all 1, and the Di are successively 1, 2, 1, 1, 4, 1, 1, 6, 1, 1, 8, .... Write a program that uses your cont-frac procedure from exercise 1.37 to approximate e, based on Euler's expansion.
Solution:
(define (nl_denoms i)
(cond ((=(remainder i 3) 1) 1)
((=(remainder i 3) 2) (final_sum (+ (quotient i 3) 1)))
((=(remainder i 3) 0) 1)))
(define (final_sum i)
(define (helper i result)
(if (= i 0) result
(helper (- i 1) (+ result 2))))
(helper i 0)
)
(+ 2 (cont-frac (lambda (x) 1.0) nl_denoms 11))
;2.7182818352059925
(+ 2 (cont-frac-iter (lambda (x) 1.0) nl_denoms 11))
;2.7182818352059925
Sep 29, 2009
Playing with recursion - string permutation
I have always had this feeling that I did not have a better hang of the concept of recursion. I know I could easily write recursive functions like computing factorial, Fibonacci series etc using recursion but when it really comes down to something outside of the norm I will instantly get this queasy feeling. So, to put an end to this, I started learning recursion and to demonstrate my learning I have put together a simple recursive function to compute the different permutations of a string with distinct characters. Given an input string, this function will emit all possible permutations of the supplied string by re-arranging the characters inside the string. Let us begin by analyzing how we would solve this problem on paper.
First, let us have a look at few sample strings and their permutations.
Input String: 'ab'
Permutations: 'ab', 'ba'
Input String: 'abc'
Permutations: 'abc', 'acb', 'bac', 'bca', 'cab', 'cba'
Input String: 'abcd'
Permutations: a + all permutations of 'bcd', b + all permutations of 'acd', c + all permutations of 'abd', d + all permutations of 'abc'
As soon as we reached a 4 characters string the permutations become unwieldy and is becoming a challenge to compute mentally. However, if we recall from our math class, we know that we can have a maximum of 4! (factorial) permutations with a 4 characters string equaling 24 different variations.
But this simple analysis has given out the solution for us. If you look closely you will notice that for a string with 4 characters, we were computing permutations by combining each character from the 4 characters string with the result of all possible permutations of the remaining string with 3 characters. Similarly for the string with 3 characters we can compute the permutations by combining each characters of the 3 characters string with the result of all possible permutations of the remaining string with 2 characters and so on.
permutation ('abcd') = a + permutation('bcd') and so on
permutation('bcd') = b + permutation('cd') and so on
permutation('cd') = c + permutation('b') and so on
permutation('b) = b (Since there is nothing to permute with just one character)
The above flow lends itself elegantly to a recursive solution. I have specified the pseudo code below.
Note the recursive call to "permutation" inside the function. Find below the implementation in Python.
I am a newbie to Python. Therefore, you may find code above that may not be the norm among pycoders.
Also, be warned, the above implementation & logic works only for string with distinct characters. If you have repetitive characters, the above logic will produce erroneous results.
First, let us have a look at few sample strings and their permutations.
Input String: 'ab'
Permutations: 'ab', 'ba'
Input String: 'abc'
Permutations: 'abc', 'acb', 'bac', 'bca', 'cab', 'cba'
Input String: 'abcd'
Permutations: a + all permutations of 'bcd', b + all permutations of 'acd', c + all permutations of 'abd', d + all permutations of 'abc'
As soon as we reached a 4 characters string the permutations become unwieldy and is becoming a challenge to compute mentally. However, if we recall from our math class, we know that we can have a maximum of 4! (factorial) permutations with a 4 characters string equaling 24 different variations.
But this simple analysis has given out the solution for us. If you look closely you will notice that for a string with 4 characters, we were computing permutations by combining each character from the 4 characters string with the result of all possible permutations of the remaining string with 3 characters. Similarly for the string with 3 characters we can compute the permutations by combining each characters of the 3 characters string with the result of all possible permutations of the remaining string with 2 characters and so on.
permutation ('abcd') = a + permutation('bcd') and so on
permutation('bcd') = b + permutation('cd') and so on
permutation('cd') = c + permutation('b') and so on
permutation('b) = b (Since there is nothing to permute with just one character)
The above flow lends itself elegantly to a recursive solution. I have specified the pseudo code below.
permutation(string)
{
myList = empty
if string.length == 1
Add string to myList
else
for each char in string
for each permutation(string-char)
Add char + permutation to myList
return myList
}
Note the recursive call to "permutation" inside the function. Find below the implementation in Python.
def permute(instr):
myList = list()
if len(instr) == 1:
myList.append(instr)
else:
for inchar in instr:
for perm in permute(redux(instr, inchar)):
myList.append(inchar + perm)
return myList
def redux(instr, inchar): outstr = '' for c in instr: if c != inchar: outstr += c return outstr
I am a newbie to Python. Therefore, you may find code above that may not be the norm among pycoders.
Also, be warned, the above implementation & logic works only for string with distinct characters. If you have repetitive characters, the above logic will produce erroneous results.
Subscribe to:
Posts (Atom)
