Solve with Python [100 selected past questions that beginners and intermediates should solve] (015 --017 Full search: Permutation full search)

1. Purpose

Solve 100 past questions that beginners and intermediates should solve in Python. The goal is to turn light blue by the time you finish solving everything.

This article is "015 --017 Full Search: Permutation Full Search".

2. Summary

Permutation problems can often be solved by using itertools well. permutaionsWhencombinationWhenproductI use it a lot, so I learned this area by trying various sample data.

3. Main story

015 --017 Full search: Permutation full search

  1. AtCoder Beginner Contest 145 C - Average Length image.png

Answer


N = int(input())
towns = [tuple(map(int, input().split())) for _ in range(N)]

total_distance = 0
count = 0
for start in range(N-1):
    for end in range(start+1, N):
        start_x, start_y = towns[start]
        end_x, end_y = towns[end]

        total_distance += ((end_x - start_x)**2 + (end_y - start_y)**2)**0.5
        count += 1

# factor = math.factorial(N)Then
# answer = total_distance * (factor * (N - 1) / count) /It becomes a factor and the formula can be transformed as follows
answer = total_distance * ((N - 1) / count)
print(answer)

There are various calculation methods here. To be honest, I enumerate all the arrangements with permutation, find the distance in all, and take the average. I think this will still work, but I tried it as an answer with a little less calculation. The policy is

  1. Sum the distances of all two point combinations
  2. The answer is this sum multiplied by `` (N -1) / number of combinations `.

is The above 2 is derived from the expression transformation left as a comment in the code.


  1. AtCoder Beginner Contest 150 C - Count Order image.png

Answer

import itertools

N = int(input())
P = tuple(map(int, input().split()))
Q = tuple(map(int, input().split()))

count = 1
for p in itertools.permutations(range(1, N+1)):

    if p == P:
        count_P = count
    if p == Q:
        count_Q = count

    count += 1

ans = abs(count_P - count_Q)
print(ans)

Believe that python's itertools.permutations will list them in lexicographic order (!) I'll write it straightforwardly. The policy is

  1. Enumerate permutations from 1 to N with itertools.permutations
  2. Count the counts to enumerate and record `count_P``` and `count_Q``` where P and Q match.
  3. The answer is the difference between the two

is. itertoolsIf you don't have one, you'll have to think a little more, but it's convenient, so I used it without thinking.


017. ALDS_13_A-8 Queens Problem

image.png

Answer


import itertools
import copy

def flag_queen_load(grid, r, c):
    for i in range(1, 8):
        if 0 <= c+i and c+i < 8:
            grid[r][c+i] = -1 #right
        if 0 <= c-i and c-i < 8:  
            grid[r][c-i] = -1 #left
        if 0 <= r+i and r+i < 8:  
            grid[r+i][c] = -1 #under
        if 0 <= r-i and r-i < 8:
            grid[r-i][c] = -1 #Up
        if 0 <= r-i and r-i < 8 and 0 <= c+i and c+i < 8:
            if grid[r-i][c+i] == 9:
                continue
            grid[r-i][c+i] = -1 #Upper right
        if 0 <= r+i and r+i < 8 and 0 <= c+i and c+i < 8:
            if grid[r+i][c+i] == 9:
                continue
            grid[r+i][c+i] = -1 #Lower right
        if 0 <= r+i and r+i < 8 and 0 <= c-i and c-i < 8:  
            if grid[r+i][c-i]  == 9:
                continue
            grid[r+i][c-i] = -1 #Lower left
        if 0 <= r-i and r-i < 8 and 0 <= c-i and c-i < 8:
            if grid[r-i][c-i] == 9:
                continue
            grid[r-i][c-i] = -1 #upper left

    grid[r][c] = 9 #myself

    return grid


if __name__ == "__main__":

    k = int(input())
    grid = [[0] * 8 for _ in range(8)]
    for _ in range(k):
        r, c = map(int, input().split())
        grid = flag_queen_load(grid, r, c)

    # 0~Try all 7 numbers in a permutation
    #Think of the generated permutations as row numbers for subscripts and column numbers for elements
    for perm in itertools.permutations(range(8)):
        copy_grid = copy.deepcopy(grid) #Use a new grid every time
        count = 0
        for row, col in enumerate(perm):
            if copy_grid[row][col] == -1:
                break
            if copy_grid[row][col] == 9:
                continue
            
            copy_grid[row][col] = 9
            copy_grid = flag_queen_load(copy_grid, row, col)
            count += 1

        if count == 8 - k: # 8-break if you put k queens
            break
    
    #Answer display
    for row in range(8):
        for col in range(8):
            if copy_grid[row][col] == -1:
                print('.', end='')
            else:
                print('Q', end='')
        print()

Originally I wrote it in Numpy, but can't AOJ use Numpy? I couldn't submit it due to an error, so I rewrote it with a normal list. The policy is

  1. First, set the chess board to `` `grid```, set the position where the queen is located to 9, the part where the queen can attack is -1, and the other blank parts are 0.
  2. Create a function `flag_queen_load ()` that updates the board when a queen is placed at a certain coordinate (r, c) .
  3. After that, try all the placements to determine if they can be placed successfully.
  4. When trying all the ways, enumerate the permutations from 0 to 7 with ```itertools.permutations (range (8)) `` `, and think of the generated permutations as row numbers for subscripts and column numbers for elements. Masu
  5. After that, if the board is -1, you can not put it, so `break```, if it is 9, it is OK, so `continue```
  6. The answer is when you can put a new queen `` `8-k``` times

is.

The function ``` flag_queen_load ()` `` is dirty, so I should have written it a little cleaner.


Recommended Posts

Solve with Python [100 selected past questions that beginners and intermediates should solve] (015 --017 Full search: Permutation full search)
Solve with Python [100 selected past questions that beginners and intermediates should solve] (010 --014 Full search: Bit full search)
Solve with Python [100 selected past questions that beginners and intermediates should solve] (024 --027 Depth-first search)
Solve with Python [100 selected past questions that beginners and intermediates should solve] (001 --004 All search: All enumeration)
Solve with Python [100 past questions that beginners and intermediates should solve] (028 --033 breadth-first search)
Solve with Python [100 past questions that beginners and intermediates should solve] (053 --055 Dynamic programming: Others)
Solve with Python [100 selected past questions that beginners and intermediates should solve] (056 --059 Shortest path problem: Dijkstra's algorithm)
[Python] I tried to solve 100 past questions that beginners and intermediates should solve [Part 5/22]
[Python] I tried to solve 100 past questions that beginners and intermediates should solve [Part7 / 22]
[Python] I tried to solve 100 past questions that beginners and intermediates should solve [Part 4/22]
[Python] I tried to solve 100 past questions that beginners and intermediates should solve [Part3 / 22]
[Python] I tried to solve 100 past questions that beginners and intermediates should solve [Part 1/22]
[Python] I tried to solve 100 past questions that beginners and intermediates should solve [Part 6/22]
Solve with Python [100 selected past questions that beginners and intermediates should solve] (005 --- 009 All search: All enumeration to reduce the number of streets by devising)
Solve with Python [100 selections of past questions that beginners and intermediates should solve] (034-038 Dynamic programming: Knapsack DP basic)
Solve with Python [100 selections of past questions that beginners and intermediates should solve] (039 --045 Dynamic programming: Knapsack DP variant)
Causal reasoning and causal search with Python (for beginners)
1st Algorithm Practical Test Solve past questions with python
Try to implement permutation full search that often appears in competition pros with python
Full bit search with Python
2nd Algorithm Practical Test Solve past questions with python (unfinished)
Learn search with Python # 2bit search, permutation search
Solve the subset sum problem with a full search in Python
About bit full search that often appears in competition pros From the eyes of beginners with python
Automatically search and download YouTube videos with Python
Let's make an app that can search similar images with Python and Flask Part1
Let's make an app that can search similar images with Python and Flask Part2
[For beginners in competition professionals] I tried to solve 40 AOJ "ITP I" questions with python
Solve simultaneous ordinary differential equations with Python and SymPy.
Crawling with Python and Twitter API 1-Simple search function