As stated in the title,
I would like you to tell me the algorithm (make an array) that uses 100 numbers from 1 to 100 each so that even or odd numbers do not last more than 4 times.
For example
x = [99,1,4,5,2,66,45...]
length(x)
→100
I would like to create something like that.
As stated in the conditions, the bad pattern is
1, Even numbers continue more than 4 times (as well as odd numbers)
x = [77, 2, 4, 3, 66, 88, 42, 72]
2, Same number (99 in the example below)
x = [99, 1, 4, 5, 2, 66, 99...]
Creating random arrays using numbers from 1 to 100 without the same number can be done using the built-in function (MATLAB), but it does not meet the conditions of bad pattern 1.
The languages I understand are python and matlab, so it would be best if you could teach me in that language, but if it is difficult, I would appreciate it if you could explain them in words.
The following generalizations are made to "even or odd, high k-1 consecutive permutations from 1 to n
For now, let's consider an even pattern, not the permutation itself.
Consider placing the numbers in order from the front.Whether odd (or even) numbers can be placed at some point depends only on the remaining odd and even numbers and how many consecutive times they are taken out, so the recursive function However, the following is not a true or false value, but a total of the odd (valid) patterns at the transition destination is returned. where So This allows you to obtain a permutation that satisfies the conditions with equal probability. where 2. can be achieved in the following ok can be determined by the following:
Also, for faster speeds, we use lru_cache to make notes. from functools import lru_cache
from ittertools import permutations, islice, cycle
import random
@lru_cache(maxsize=None)
defok(x,y,xz,yz,k):
# Do not line up more than k in a row.k.a. row.
if x<0 or y<0 or xz>=koryz>=k:
return 0
# Ok when you're done with everything
elif x == 0 and y == 0:
return1
# Other than that, check if you can select one of the odd and even numbers and transition to a valid state.
else:
return ok(x-1,y,xz+1,0,k)+ok(x,y-1,0,yz+1,k)
m=ok (even numbers in the original permutation, odd numbers in the original permutation, 0, 0, k) is the total number of even and odd patterns containing at most k-1 consecutive even and odd numbers.get_nth using ok to obtain the number of patterns at the transition destination:#i-th pattern selection function
# Cur contains an odd pattern
def get_nth(x,y,xz,yz,k,i,cur):
if x == 0 and y == 0:
assert(i==1)
return cur
c=ok(x-1,y,xz+1,0,k)
# There are c patterns where the current position is even.
# So if it's i<=c, I'll pick an even number and move on.
if i<=c:
cur.append(0)
return get_nth(x-1,y,xz+1,0,k,i,cur)
# Otherwise, you choose an odd number and move on (but you need to subtract the number of patterns c when you make it even).
else:
cur.append(1)
return get_nth(x,y-1,0,yz+1,k,i-c,cur)
defgen(n,k):
m=ok(n//2,(n+1)//2,0,0,k)
# i [ select [1,m] uniformly
i=random.randint(1,m)
# calculate the i-th pattern
pat=get_nth(n//2,(n+1)//2,0,0,k,i,[])
# Shuffle even and odd rows, respectively
numbers = [[2*i+2 for i in range(n//2)], [2*i+1 for i in range(n+1)/2)]]
for i in range(2):
random.shuffle (number[i])
# arrange the numbers according to the pattern of
l = [ ]
For bin pat:
l.append(number[b].pop())
return l
gen(n,k) gives one permutation that satisfies the condition.
It looks like this when I actually use it.In[10]: print(gen(15,3))
[15, 1, 2, 12, 11, 8, 13, 3, 6, 7, 4, 10, 9, 14, 5]
In[11]: print(gen(15,3))
[9, 10, 13, 6, 7, 14, 5, 8, 4, 15, 1, 2, 11, 12, 3]
In[12]: print(gen(100,4))
[22, 68, 71, 28, 12, 19, 14, 53, 85, 6, 7, 88, 62, 75, 65, 32, 64, 59, 77, 100, 17, 1, 95, 48, 73, 60, 2, 91, 81, 10, 86, 83, 42, 90, 76, 99, 13, 4, 92, 34, 11, 35, 25, 52, 94, 63, 39, 31, 72, 23, 3, 93, 26, 40, 79, 47, 51, 8, 27, 89, 37, 98, 50, 70, 87, 38, 66, 5, 15, 30, 74, 57, 67, 16, 46, 29, 9, 96, 56, 84, 69, 20, 36, 49, 82, 44, 41, 43, 80, 58, 18, 55, 24, 33, 61, 78, 97, 54, 45, 21]
奇 → odd number
× → even number
If so,
〇 】 「××××××××××××××××××××××××××××××××××××××××××××××××××× followed by
[Odd set] and even set.
The number of sets must always be equal or the difference must be 1.
Otherwise, there will be more than 4 consecutive ones.
If it's the same value, either odd or even number comes first
〇 】 「×××××××××××××××××××××××××××××××××××××××××××××××××××××××××××
××× 【 〇×××××××××××××××××××××××××××××××××××××××××××××××××××××××××
If the difference is 1, the larger one comes first.
One more odd number
〇 】 「×××××××××××××××××××××××××××××××××××××××××××××××××××××××××××
One more even number
"""××"" [ 】] ""×××"" [ 】 「] ""××"" [ 】 ···]… ""××""
So the first thing you need to do is decide how many pairs you want to make.
It is a combination of 3 or less numbers from 1 to 100, so
Minimum number of pairs is 50/3 = 16 or more 217 pairs
Maximum number of sets is 50/1 = 50/50 pairs
First, we randomly decide the number of sets A (17 to 50).
Also, the number of pairs B is randomly determined from -1 of the number of pairs A, equivalent to the number A, and +1 of the number A.However, make sure that the number of sets B is within the range of 17 to 50.
Then, we randomly decide which set A or B is even or odd.
For your convenience, I think the following conditions will be established.
[ ] [ ] [ ] [ ] [ ] [ ] [ ] ... Group A
Group B (AorA+1 or A-1)
An image with an empty box.
Then, when the set number AB and odd even numbers are determined, assign a number to the set, but since it must be at least one, let's first assign one number randomly to each set of odd even numbers to all boxes.
After that, I think you can randomly allocate the remaining numbers so that they don't reach more than four.
The next step is
If the number of sets is the same, odd and even numbers are determined at random, so you can arrange them from A.
If there is a difference in the number of sets, start with the larger number of sets.
There may be some functions or formulas that can support the allocation of values depending on the language, but I don't think there's much difference in speed, and I don't think I need to worry about speed or performance this time.
© 2024 OneMinuteCode. All rights reserved.