I am trying to learn about algorithmic thinking in my spare time from a book I got.

I am thinking about scenarios and trying to solve them using pseudocode in order to learn but I cannot approach this idea below. I am thinking of doing this with a nested loop but I don't know how to begin. Can you please assist?

If we have a 1d array that mentions how many times each position should be repeated for example: With N = 5, the 1d array is z = 2,1,1,3,2 Based on that, we should populate a new array with the times each number appears. Therefore, based on z we should have a 1d array A = 1,1,2,3,4,4,4,5,5.

Explanation: the first position of z has the number 2. Therefore, in the A array the number 1 should appear two times. continuing the number two of array z has the number 1, therefore the number 2 in the array A should appear only once, and so one for the rest numbers. So there is a pattern between the two arrays.

NOTE: This should not be using any functions or turning values to string and multiplying them. I am interested in the theoretical side of it and want to learn how to think for such problems.

UPDATE

Would it help if we have

an array with unsorted items:

 A: 2,3,1,2,4

and z where calculates how many times each position is mentioned.

z: 1,2,1,1

can we create a new array that will make the the content of A sorted based on the content of z?

CodePudding user response：

You can use list comprehension with nested loop:

result = [i 1 for i, freq in enumerate(z) for _ in range(freq)]

Without list comprehension:

result = []
for i, freq in enumerate(z):
    result.extend([i 1]*freq)

Without any functions (less Pythonic), using = and * operators for lists:

result = []
i = 1
for freq in z:
    result  = [i] * freq
    i  = 1

Without * operator for lists:

result = []
i = 1
for freq in z:
    while freq > 0:
        result  = [i]
        freq -= 1
    i  = 1

= [i] is really a clumsy way to append(i), but at least it avoids the function, which you seem to be looking for.

CodePudding user response：

First of all we can try to find what will be the final array size that we will be getting. The final array size will be the total sum of numbers given in the z array. Given z = [2,1,1,3,2], then the total size of the result array will be 2 1 1 3 2 = 9

So our result array will be of size 9.

Now we need number 1 to be repeated 2 time. Number 2 to be repeated 1 time and so on. So we can first traverse through the given array z and take out each of the number which is telling how many time we need to repeat the number. So using another loop until we reach that number, we can keep on adding the number we needed in the resultant array.

The code will look like this in java, can use the same logic in Python also :

int [] generateResult(int [] z, int n) {
    int sum = 0; // to find the length of result array
    for (int i=0; i<n; i  ) {
        sum  = z[i];
    }
    int [] result = new int [sum];
    int indexForResult = 0;
    int numberToInsert = 1;
    for (int i=0; i<n; i  ) {
         int repetition = z[i];
         // repeat adding the number 
         for (int j=0; j<repetition; j  ) {
             result[indexForResult  ] = numberToInsert;
         }
         numberToInsert  = 1;
    }
    return result;
}

CodePudding user response：

The question can be easily done using a nested loop. Pseudocode:

INT k -> 0
OUTER LOOP (i->0 TO N-1, WITH INCREMENT OF 1 EACH TIME)
{
    INNER LOPP (j->0 TO z[i]-1, WITH INCREMENT OF 1 EACH TIME)
    {
      A[k] = i 1
      k = k   1
    }
}

i, j -> Iterators
k -> Maintains Index
N -> Number of Elements in z.
z[i] -> Value at Index i in Array z.

NOTE: You have to traverse the z Array once to count the total sum of elements in it, this will give the size of Output array A.

z = [2, 1, 3, 4] # Any Input
sum = 0
# Calculating the sum of all elements of z array, so that we can get to know 
# number of elemnents of A array.
for i in range (0 , len(z)): 
    sum = sum   z[i]
A = [None]*sum
k = 0
for i in range (0 , len(z)): # Outer loop just runs over to iterate over the z array
    for j in range (0 , z[i]): # Inner loop will make sure index i is getting repeated z[i] times 
        A[k] = i 1
        k = k   1
print(A)

You can also altogether avoid calculating the sum if you use the append function.