Hi, I am looking for a function that can help me d...

# getting-started

[Esa]

Hi,
I am looking for a function that can help me do the following:
I have a collection (unsorted) of elements that I need to transform. After each transformation I will use the result to lookup the next element to transform.

Are there any standard functions that does something like this, or will I need to create my own Collection<T>.mapUnsorted function?

[nanodeath]

what does it matter that it's unsorted?

[Esa]

Because I only know which element to go for next after I've already processed the previous. The map function that already exists doesn't account for that

[itbhp]

@Esa can you provide an example? Or some examples?

[nanodeath]

it's not really a map...examples would help, yeah

[Esa]

I don't have an implementation of this yet as I first started looking for a function to solve it rather than solve it imperatively with a do/while-loop. I'm sure it can be solved rather easily imperatively, but I'd want to try this as an algorithmic exercise for now :)

So the problem is something like this:
Assume you have a list of n people, with each person having 1 computer each. Each computer will only work with the correct person. However, all computers are with the wrong person and need to be swapped, but you can only swap one at a time, and nobody can be without a computer. You have 1 computer that is not in use that can be used temporarily to free up the computer of a person to allow that person to return their current computer.

Given all of that, what'd be the best approach to swap every computer in one go?

That's what got me thinking about a function that transforms one element (swaps a computer) and uses the result (returned computer) to look up the next element (person who needs the computer of the previous person) to be transformed (swapped).

[Esa]

So I started on something like this, but haven't been able to get it working yet and that's where I am currently

[Esa]

This would use the predicate to find{} the next element of the collection using the result of transform. That already smells like horribly inefficient code, so I guess it's not exactly the best way to solve it..

[Esa]

Does this make sense? Am I talking gibberish?

[Esa]

@itbhp @nanodeath

[itbhp]

How would you solve this problem in pseudo code? Think about it and then try to improve you solution.

Or start with a simple solution and then generalize it.

You can model this problem as an array: each index is a person and the value of A[i] can be though as a number from 1..N representing the computer. You are saying that A[0] should have value 1, A[1] = 2 and... A[n-1] = N. At the beginning the array is unsorted and you have to sort it only with swaps. There is a classical algorithm to do it: Bubble Sort.

To implement this with a map function I have to think about it.

Have I understood the problem correctly?

[itbhp]

The way you are describing what to to do seems like an Insertion Sort

[itbhp]

In the end it will sort the collection but it will not satisfy the request to do it only with swaps

[Esa]

Yeah sounds like, except in this case you can't just assign a value to the key. That value may already be in use with another key which means you need to free up that value by assigning a different value to that key (the 1 free computer I mentioned in the example). So if you're doing like a bubble sort and comparing element n with n-1 you may not end up with the correct pairing as n could very well belong with n-7. There's a big chance I misunderstood you as I am not familiar with bubblesort or insertion sort

[itbhp]

You can use a supporting array to do the map.

Array A contains the current computer person mapping, person i has the computer A[I].

The solution (which computer should have every person) can be stored in another array B, so B[i] will store the number the i-th person should have, given the pc are numbered from 1 to n.

This modeling is very different and the solution is not a simple sorting.

I have to think about it.

For sure understanding the problem first or having a test examples could help to find the right solution

[Esa]

Okay no worries, I can type up an example. I think you understand it properly though. 🙂 give me a few minutes

[Esa]

pasted a little something here: https://pastebin.com/jLz3yCiW

[Esa]

So to reiterate, the problem I'm trying to solve would be extracting that into a Collection extension function of generic type

[Michael de Kaste]

who's to decide what the very first value of your outcome should be btw? I thinked I missed that

[Esa]

Currently I'm just doing if (this.isNotEmpty()) Collection.first() for the initial transformation, if that's what you meant

[Michael de Kaste]

so the predicate is finding the next one by the result of the previous, but the very first argument is ALWAYS the first one?

[Michael de Kaste]

that doesn't sound unsorted to me 😉

[Michael de Kaste]

semi-sorted 🙂

[Esa]

Hm no in this instance it doesn't really matter which one you start with, that's why I just took the first() one. Could've just as well been last() or shuffled().first() 😛 Or even provided as an argument in the extension function

[Esa]

Other than that your understanding of the predicate is correct

[Michael de Kaste]

• That's still not ordering, as an ordering of a list should be disjointed from the initial ordering, but in this case it matters what you consider the "initial value" and in what order you traverse the list.
• What if multiple elements satisfy the predicate? What if a previously handled element satisfies a subsequent predicate? A simple given previous outcome, what is the next one? isn't an ordering.
• It seems you'd like to find a "path" of some sort of a list, which is an unique enough operation to not qualify it as an extension function, but I'm not stopping you.
• Your function signature seems correct, so what part do you have troubles with?

[Andrew]

Still trying to understand the exact problem or use case, it would help to have a concrete example with 1) input 2) example code that does the map in a for loop or whatever 3) output you desire