Python based backtracking method subset tree template to solve the selection row problem example

In this article, an example of Python based on the backtracking method subset tree template to solve the problem of selecting rows. Shared for your reference, as follows:

concern

Pick m elements from the n elements to arrange, and repeat each element at most r times. where m ∈ [2,n] and r ∈ [1,m].

E.g., pick 3 elements out of 4 and arrange them in such a way that each element can be repeated up to r times.

analyze

The length of the solution x is fixed at m.

For solving x, the element x[0] in the 0th position is first ranked, and then the element x[1] in the 1st position is ranked. We regard the latter as a state of the former, i.e., x[1] is a state of x[0]!

In general, think of x[k] as a state in the state space a of x[k-1], and all we have to do is to iterate through all the states of a[k-1].

Then, just apply the subset tree template.

coding

'''
Selection and Arrangement Problem
Select m elements from n elements to be arranged, and each element can be repeated at most r times. Where m ∈ [2,n] and r ∈ [1,m].
Author: hhh5460
Time: June 2, 2017 09:05 pm
Disclaimer: This algorithm is copyrighted by hhh5460
'''
n = 4
a = ['a','b','c','d']
m = 3  # 3 out of 4
r = 2  # Up to 2 repetitions per element
x = [0]*m  # A solution (m-element 0-1 array)
X = []   # A set of solutions
# Conflict detection
def conflict(k):
  global n, r, x, X, a
  # The element x[k] within a partial solution cannot exceed r
  if x[:k+1].count(x[k]) > r:
    return True
  return False # Conflict-free
# Implementing selection and ranking problems with subset tree templates
def perm(k): # Reach the kth element
  global n,m, a, x, X
  if k == m: # Beyond the endmost element
    print(x)
    #(x[:]) # save (a solution)
  else:
    for i in a: # Traverse the state space a of x[k-1] and leave the rest to the pruning function!
      x[k] = i
      if not conflict(k): # Pruning
        perm(k+1)
# Testing
perm(0) # Arranged from x[0]

rendering (visual representation of how things will turn out)

More about Python related content can be viewed on this site's topic: thePython Data Structures and Algorithms Tutorial》、《Python Socket Programming Tips Summary》、《Summary of Python function usage tips》、《Summary of Python string manipulation techniques》、《Python introductory and advanced classic tutorialsand theSummary of Python file and directory manipulation techniques》

I hope that what I have said in this article will help you in Python programming.