Programmer’s essential algorithm – permutation and combination

[TOC]

Remember permutations and combinations?

  • In high school, the most common contact than permutation combination, after all, the college entrance examination must be tested. Let’s remember what the formula for these two is:

    Permutation and combination formula

If you still have an impression of this, it shows that everyone’s foundation is not bad. So the question is, we’re all computer students, how do we simulate this process with a program, so that we can list all the possible permutations and combinations?

Realization of full permutation

  • Brute force solution (not desirable, not desirable)

    The first thing you might want to do is to iterate through a nested for loop. If the loop is not equal to each other, you can print it directly, like this:

    def force(a):
    data = "abc"
    for i in range(len(data)):
        for j in range(len(data)):
            for k in range(len(data)):
                ifdata[i] ! = data[j]anddata[j] ! = data[k]anddata[k] ! = data[i]: print(data[i],data[j],data[k])if __name__ == '__main__': force() /* output a b c a c b b a c b a c a c a b b a */Copy the code

    This looks fine, but there are a few disadvantages. If we want to do a full permutation of ABcd instead of a full permutation of ABC, then we have to modify the source code to add a for loop, and if the permutation is too many, then the loop is too many.

  • Recursive solution

    The above solution is a bit inelegant, so how can we find all the permutations without modifying the source code? Let’s start with a picture:

    Write the picture description here

    As for the permutation of ABC, when we make the permutation, we can first consider the possible conditions of the first digit, as shown in the figure above, and then arrange the following two digits in the same way, so we can easily achieve the full permutation through recursion.

    def rank(data, step):
    if len(data) == step+1:
        print(data)
        return
    else:
        for i inRange (step, len(data)): data[step], data[I] = data[I], data[step] // Rank (data, step +1Data [step], data[I] = data[I], data[step]if __name__ == '__main__':
    data = list("abc")
    rank(data, 0)Copy the code

    If you run the code above, you’ll get exactly the same result as the brute force solution above, and this time you don’t need to modify the source code if you need to do all the permutations, and you only use one loop (though recursively it’s not as efficient as multiple loops ^-^), but at least the code looks elegant.

  • Solve the repetition problem of full permutation

    If you are careful, you will notice that there is a problem with the above code. If there are duplicate elements in the array, the result will also have duplicate permutations, which we do not want to see. So how do we solve this problem?

    To solve this problem, we first need to know where the problem came from. Again, referring to the picture above, let’s modify it slightly:

    Write the picture description here

    Take the CAC for example:

    • When we start with the first c, we need to do a full permutation of ac, okay

    • When we start with a, we need to permutation cc, no problem

    • When starting with the second c, we need to complete the ca permutation, this problem, ac and CA permutation is not the same, and the beginning is the same, this must have repeated ah, we modify the source code slightly:

      def is_equal(data,left,right):     Check if there is any equality between left and right, if there is any indication of what has been done on this
    for i in range(left,right):       # all sorted
        if data[i] == data[right]:
            return True
    return False
def rank(data, step):
    if len(data) == step+1:
        print(data)
        return
    else:
        for i in range(step, len(data)):
            if is_equal(data,step,i):  # Add a judgment
                continue
            else:
                data[step], data[i] = data[i], data[step]
                rank(data, step + 1)
                data[step], data[i] = data[i], data[step]
if __name__ == '__main__':
    data = list("bcc")
    rank(data, 0)Copy the code

      Ok, so running the above code will not have repeated problems, here may need partners to think more, but it is still very simple.

Combinatorial problems

  • Problem description

    I have an array [1, 2, 3, 4, 5, 6] and I want to pick three of them at random.

  • solution

    It’s recursive, because we don’t know how many times we’re going to loop, but how do we recurse?

    Write the picture description here

    Don’t worry, let’s say we want to pick three elements from the array above.

    Let’s start with the first element. For the first element, we have two choices: yes or no.

    If we do, then we have one less element to select, we just need to select two from the following elements.

    If not, let’s continue with the second element, at this point we still have to choose three (originally wanted to draw a diagram to demonstrate, but this diagram seems a bit complicated, I am a novice drawing will steal lazy).

    def combine(data, step, select_data, target_num):
    if len(select_data) == target_num:   # Select enough elements, print and return
        print(select_data)
        return
    if step >= len(data):               # no more elements selected and not enough
        return
    select_data.append(data[step])             Select the current element
    combine(data, step + 1, select_data, target_num)
    select_data.pop()                         Don't forget to delete the selected elements first
    combine(data, step + 1, select_data, target_num) Do not select the current element
if __name__ == '__main__':
    data = [1.2.3.4.5.6]
    combine(data, 0[],3)Copy the code

    Running the code above gives you all the possible combinations, and it’s a little more elegant. But also when you have duplicate elements in an array you also have duplicate combinations, so how do you solve that? I’ll let you think about it for yourself.

conclusion

  • Permutation and combination algorithm is still very close to our life, in a variety of algorithms, projects and interviews will often meet, so it is also a programmer’s necessary algorithm, if there is a problem with the above code, you are welcome to leave a message with the author private communication, learning and communication together progress. You can also follow my wechat official account:

    ​