Shuffle and Number of Good Pairs

excerpt: This covers the basic building blocks such as writing into string like array, nested for loops and nested loop with one index. tags: writing-into-string-array nested-for-loop nested-loop-with-one-index swap

This article covers the following basic building blocks:

Writing into String like Array
Nested For Loops
Nested Loop with One Index

Shuffle Array

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
def shuffle(a)
  n = a.size-1
  
  for i in (0..n)
    j = rand(0..n)

    a[i], a[j] = a[j], a[i]
  end
end

a = [1,2,3,4,5]

shuffle(a)

p a

Shuffle String

Implement a method to shuffle a given string.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
# @param {String} s
# @param {Integer[]} indices
# @return {String}
def restore_string(s, indices)
  n = s.size
  result = '0' * n

  for i in (0..n-1)
    result[indices[i]] = s[i] 
  end
  
  result
end

s = "aiohn"
indices = [3,1,4,2,0]

p restore_string(s, indices)

Building Blocks

Writing into String like Array

Print all pairs of numbers in an array.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
def pairs(a)
  n = a.size
  
  for i in (0..n-2)
    for j in (i+1..n-1)
      p "(#{a[i]}, #{a[j]})"
    end
  end
end

a = [1,2,3,1,1,3]

p pairs(a)

Building Block

Nested For Loops

This can be applied to solve the problem: Number of Good Pairs. Just add a counter to the nested for loop that has the right bounds for the start and end indices.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
# @param {Integer[]} nums
# @return {Integer}
def num_identical_pairs(nums)
  total = 0
  
  for i in (0..nums.size-2)
    for j in (i+1..nums.size-1)
      if nums[i] == nums[j]
        total += 1
      end
    end
  end
  
  total
end

Iterate through the list and swap adjacent elements if they are in the wrong order.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
def sort(a)
  n = a.size
  
  for i in (0..n-2)
    for j in (i+1..n-1)
      if a[i] > a[j]
        a[i], a[j] = a[j], a[i]
      end
    end
  end
end

a = [3,8,2,0,9,1,4]
sort(a)

p a

The inner loop starts from 1 more than the outer loop index and ends at the last element. The outer loop starts from the first element and goes till the element before the last one. The structure of the program is the same as the previous problem Number of Good Pairs. This algorithm is called the Bubble Sort.

We can rewrite the program to use one index variable:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
def sort(a)
  n = a.size
  
  n.times do
    for j in (0..n-2)
      if a[j] > a[j+1]
        a[j], a[j+1] = a[j+1], a[j]
      end
    end
  end
end

a = [3,8,2,0,9,1,4]
sort(a)

p a

The inner loop index starts at 0 and ends at one element before the last one.

Building Blocks

Nested for Loop
Nested Loop with One Index