A subset of a list with the elements {a,b,c} is {a,b}. The task is to find all possible subsets. Sets in programming languages are usually not ordered. Therefore, the set {a,b,c} is equivalent to {b,c,a}.
The idea for the solution is a nested for-loop that iterates over the results again and again, starting with one empty ([]) result.
The goal of this task is to find all possible permutations of numbers in a list. For example, [1,2,3] can become [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]. Mathematically, the number of possible permutations without using duplicates is n! where n is the number of unique elements in the list.
This problem can best be solved by using backtracing and recursion. The general idea is to put all possible digits in the beginning and then cut off the rest of the list and repeat the first step. Later, the list is assembled. The algorithm stops if there is only one item in the list because the only possible permutation is with itself. The other special case that needs to be handled is the empty list which must return the empty list itself.
Great tutorial how to use Devise with Rails 7 and Turbo: Youtube.
The task is to print all case permutations of letters from strings that can include digits and letters. For example, a1b becomes a1b, a1B, A1b, A1B.
The trick here is to realize that there are 2^n possible permutations where n is the number of characters, excluding digits.
To find the exact element or the next element that is greater than the target, use the following code. This algorithm returns an invalid index if the element that is searched for is greater than the greatest element in the array. This needs to be manually checked with s(items, target) == len(items).
def s(items, target):
l = 0
r = len(items)
m = (l + r) // 2
while l < r:
if items[m] == target:
return m
elif items[m] <= target:
l = m + 1
elif items[m] > target:
r = m
m = (l + r) // 2
return m
l = [1,2,3,5,6,7,8,20,30,40,50]
targets = [0, 3, 4, 11, 12, 20, 30, 38]
for target in targets:
idx = s(l, target)
print(f"[{target:02}] Index: {idx} => {l[idx]}")return m - 1 instead. In the smallest case this will return -1 which means that the element searched for is smaller than the smallest on in the list. The resulting code looks like this:
def s(items, target):
l = 0
r = len(items)
m = (l+r) // 2
while l < r:
if items[m] == target:
return m
elif items[m] <= target:
l = m + 1
elif items[m] > target:
r = m
m = (l+r) // 2
return m - 1