2
$\begingroup$

Background:

(I’m a complete beginner in computer science in general, so I do apologise if my question is not formulated in a sensible way. E.g. I have avoided technicalities in formulating my problem, but perhaps this causes issues. I'm willing to edit accordingly if so).

I’m trying to get to grips with the way that algorithms are/can be used in economics. I think I understand the (very) basics of how sorting algorithms and clustering algorithms could apply to some problems, but there is a (seemingly) elementary problem which I can’t find a well-known algorithm for.

The problem:

Suppose my entire input consists of a set of different quantities of two types of good. For example, apples and oranges:

Input: { 1 apple, 1 orange, 10 apples, 10 oranges }

Is there a well-known algorithm which can arrange these inputs by type of good, such that the output is the following two sets?:

Set 1 (apples): { 1 apple, 10 apples }

Set 2 (oranges): { 1 orange, 10 oranges }

Clustering and sorting algorithms do not seem to be appropriate:

From my (very, very basic) knowledge of clustering algorithms, they would not be appropriate here, as clusters are meant to represent closeness of data points in space. But, if I were to plot these goods as data points, I would have a representation of their values, whereas I'm trying to group them via their categories.

I also don’t think that a comparison based sorting algorithm would work, as these algorithms produce an ordering (total preorder) of the values input. Whereas, again, I'm trying to group them via their categories.

Is my definition of algorithm the issue?

Perhaps I'm misunderstanding the type of thing that can be input into an algorithm? Cormen et al. (Introduction to Algorithms, 2009, §1.1) informally define an algorithm as

...any well-defined computational procedure that takes some value, or set of values, as input and produces some value, or set of values, as output.

So perhaps an algorithm can only take numerical values as an input and not numerical values attached to a category label (like 'apple', or 'orange')?

I’d be very grateful for any help :)

$\endgroup$
  • 1
    $\begingroup$ If you care about listing the output for apples in increasing order (like $\{1,10\}$ rather than $\{10,1\}$) then sorting can be used; assign "apples: 1" and "oranges: 2" then represent your data as ordered pairs where the fruit's code is the first coordinate and the quantity is the second: (1,1), (2,1), (1,10), (2,10). Then after you sort you can bunch things together $\endgroup$ – Matthew C Dec 1 '19 at 23:29
  • $\begingroup$ If you don't care about the ordering within a fruit, then you could still do the above, but a faster algorithm is as follows (just replace color by fruit) medium.com/@interviewprep/… which has running time linear in the input with constant equal to the number of different fruits $\endgroup$ – Matthew C Dec 1 '19 at 23:31
  • $\begingroup$ The last algorithm (dutch national flag sort) I should point out is well-known; it puts things of the same category together and also preserves the order that they were originally $\endgroup$ – Matthew C Dec 1 '19 at 23:33
1
$\begingroup$

An algorithm can be seen as the steps needed to go from a well defined type of input to some well defined output. The input can therefore be everything that one can represent within a computer.

In the algorithm you are asking for it seems like the input has already been classified as specific good as in apples are already classified as apples, had it not been defined one could use clustering to find out what separates the types of goods from each other depending on the data of each entry of a good in the database. That means that clustering is a way of data mining.

One way of solving your problem could use sorting like this:

1: def separate_goods(List S):
2:    sort S on the type of good
3:    A := a list
4:    B := a list
5:    current_type := S[0].type
6:    B.add(S[0])
7:    i := 1
8:    while(i < length(S)){
9:       if(current_type == S[i].type):
10:          B.add(S[i])
11:          i := i + 1
12:      else:
13:          A.add(B)
14:          B := a new list
15:          B.add(S[i]
16:          current_type := S[i].type
17:          i := i + 1
18:   }
19:   A.add(B)
19:   return A

The idea behind this algorithm is to first sort the input list such that all the apples are next to each, the oranges are next to each other and so on. From there we can go through the list and put all apples in a list together (the list B), then add that list to A, which simply just stores a list for each type of good.

When we go through the list (in the while loop) and sees that we go from a good of type say apples to another of type orange, then know that we finished collecting apples (since they are all together due to the sorting) and we can therefore add the list B of all the apples to list A. Then we make B contain a new list for all goods of type oranges and continuous through the list adding goods of type oranges until we either have categorized all goods or finds a new type of good.

This is not the most effective algorithm one could make, however it illustrates that sorting can be used to solve this problem.

I'm not sure if this answers your question however feel free to reach out to me :) This does not answer your question, here is another try:

Your problem is somewhat simple and can be solved in many ways, a particular fast way would be to use a hash table. Here you could hash each entry on the type of good, with this you can then access a list of all apples by using apple as key. I believe there is a chapter in Cormen et al about hashing that explains how this is done :)

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.