Obtaining lists from an array

Question

Let's say my array contains integers. I'd like to create lists, so that every list contains indexes where a particular value occured in the array. For instance, if the array was 5,0,3,5,2,5,3, we would have 4 lists (as there were 4 values):

value 5: 0, 3, 5

value 0: 1

value 3: 2, 6

value 2: 5

Currently I am attempting to figure out the highest value (in this case 5). Therefore, I create 5 lists and just add the index to the appropriate list (i.e. the 5th element of the array is 2, so I add index 5 to the 2nd list). The problem is that I created 5 lists, but there are actually 4 needed (we don't have 4 anywhere, so one list will be created unnecessarily).

Could anyone suggest a more efficient method?

Answer 1

One approach is to lazily map from element values to lists with a dictionary. On first appearance of element, create list. On future appearances, reuse corresponding list.

If you're fine with doing two passes over the input and don't want associative dictionaries, keep a list of your offset lists, and maintain an array mapping from element value to list index.

[(0,0), (1,1), (2,2), (3,3), (4,n/a), (5,4)]

This will incur an additional indirection on element lookup, but may be worth it if you expect sparseness in your values. At this point of complexity, just use a dict of lists already unless you've got something against dicts.

Answer 2

I think your approach is just fine.

You are concerned about getting 5 lists because biggest number is 5, so you can use a map with the value. The map's keys are the unique values of the array.

Here is a concrete code suggestion in JavaScript. You can try it easily in any browser debug console, just copy it into the console:

// 1. Create a test array
var mainList = [5,0,3,5,2,5,3];

// 2. To get a map, we need some unique() function for an array:
function unique(rawArray) {
    var arr = [];
    for(var i = 0; i < rawArray.length; i++) {
        if(arr.indexOf(rawArray[i]) < 0) {
            arr.push(rawArray[i]);
        }
    }
    return arr; 
}

// At this point, you get for mainList:
// [5, 0, 3, 5, 2, 5, 3]

// And for unique(mainList);:
// [5, 0, 3, 2]

// 3. Now we create a function to get the index lists:
function createMaps(uniqueList, mainList) {

    // Create and init maps.
    var maps = {};

    for (var u=0; u<uniqueList.length; u++) {
        // Create a map entry and init it with an array.
        maps[uniqueList[u]] = [];

        // Fill the array with indices.
        for (var i=0; i<mainList.length; i++) {
            if (mainList[i] == uniqueList[u]) {
                maps[uniqueList[u]].push(i);
            }
        }
    }

    return maps;
}

// 4. Now let's put the thing together:
var uniqueList = unique(mainList);
var maps = createMaps(uniqueList, mainList);
// (end of script) 

Maps will look like this:

Object {0: Array[1], 2: Array[1], 3: Array[2], 5: Array[3]}
0: Array[1]
    0: 1
2: Array[1]
    0: 4
3: Array[2]
    0: 2
    1: 6
5: Array[3]
    0: 0
    1: 3
    2: 5

Which is exactly what you wished. You see, your idea is fine.

Finally, you mentioned a "more efficient" way. This is not very specific. To get concrete answers, try to test your idea against scenarios:

• What happens to all your index lists if you remove a value from your main list? --> Many lists must be updated.
• dito : What happens to all your index lists if you add / insert / swap ... values into the main list?
• How is the performance of building a set of lists?
• What happens if you wish to combine values for indices (e.g. like you have combined indices in a relational SQL table)? How much resistance do you feel from your model?

and so on. Like this, you will see different aspects of "efficient".

Answer 3

This is my approach. Probably the same as the others, but in Java :) We iterate through all inputs, look up in our map if we already created a list for this input value, if not we create a new list. Then we just add the index of the value to the list.

public Map<Integer, List<Integer>> uniqueList(int...input) {
    Map<Integer, List<Integer>> resultMap = new HashMap<>();
    for(int i = 0; i<input.length; i++) {
        List<Integer> resultList = resultMap.get(input[i]);
        if(resultList == null) {
            resultList = new ArrayList<>();
            resultMap.put(input[i], resultList);
        }
        resultList.add(i);
    }
    return resultMap;
}

Answer 4

This is an excellent opportunity for a recursive data structure that uses polymorphism. I would make a sorted list of sorted lists. Double linked list implemented with a bubble sorted insert. The backplane list would needs to hold nodes that had a data entry and a list entry. The secondary lists would only need data entries in its nodes.