Need help in building the algorithm, looking for a...

# getting-started

[zain]

Need help in building the algorithm, looking for an optimum version of it,

The logic for creating the fixture is in pairs. You have to form a pair of two teams in a random                                     
fashion. For example - If I have 4 teams - T1, T2, T3, T4. I can have: 
 
(T1 vs T2) & (T3 vs T4) 

OR 
(T1 vs T3) & (T2 vs T4) 

OR 
(T1 vs T4) & (T2 vs T3) 
 
*Your function should accept any number n, where n is an even number > 0 and return you n/2                               
pairs/tuples*

[Joffrey]

What is your current attempt?

[zain]

Let me share you my snippet

[zain]

@Joffrey I barely started, getting confused

[Joffrey]

Your algorithm doesn't need to return all possible pairs combination, just one combination of pairs at random. One way to do it is to first randomize the list, and then build pairs with consecutive elements from the list. I can give you a way to do it, but depending on what you're learning or why you're learning it, it might not be helpful. For instance:

val randomPairs = (1..n).shuffled().chunked(2)

[ephemient]

I think you mean something like .windowed(2, 2) { (x, y) -> x to y }, as .zipWithNext() produces overlapping pairs

[Joffrey]

Right. I got carried away with the nice zipWithNext pairs, but I meant the behaviour of chunked() actually, it doesn't return a Pair type per se but we don't really know the required output type tbh, so lists of 2 elements might be enough

[zain]

If every time we randomize looks like good solution, I'm learning it for optimization because in my solution I was doing and then checking it.

val randomIndex = Random.nextInt(teams.size)
val team = teams[randomIndex]

[ephemient]

the trouble with that is you need to remove each random element after you pick it, so you don't pick it again. it's doable but costly

[zain]

@Joffrey From the output point of view it is mentioned to have pairs or tuples List<Pair<Any,Any>> something like this

return you n/2                                pairs/tuples

[ephemient]

.windowed(2, 2) { (x, y) -> x to y } or .chunked(2) { (x, y) -> x to y } both give you List<Pair<T, T>>

[ephemient]

in any case, what you should probably learn is what .shuffled() itself does, which is a Fisher–Yates shuffle

[zain]

Shuffled randomizes the list items right?

[Joffrey]

The english word "pair" refers to 2 elements, it doesn't mean they have to be returned in a type called Pair. A list of 2 elements is also a pair or tuple. That's what I meant by "the output type is unspecified".

That said, as @ephemient pointed out, if you you really want the Pair type you can use the overload of chunked that takes a transform lambda. I don't like windowed() for this because its semantics is in general to have a sliding window with overlaps, and using it with the same value for window size and step is better expressed by chunked IMO

[ephemient]

like many kotlin.collections functions, there are two variants: there is .shuffle() which will randomize a mutable list's elements, and .shuffled() which returns a new list with a random disarrangement of the original's elements

[ephemient]

chunked() works in this scenario as it is stated that the input n is even; in more general cases I prefer windowed() because you can choose how to handle odd elements (if you enable partial windows)

[zain]

chunked() internally uses windowed()
Since Kotlin 1.2

[ephemient]

yes, chunked() is a convenient special case of windowed()

[ephemient]

you don't always need the most general function

[zain]

I didn't understand how to transform chunked to return type Pair, should I map() it?

[Joffrey]

There is an overload of `chunked` that takes a lambda which acts as if you used map
@ephemient has shown it already:

val randomPairs = (1..n).shuffled().chunked(2) { (x, y) -> x to y }

This lambda takes each "chunk" (list of 2 elements) as input, destructures them into their first and second element by using (x, y) (with parentheses syntax), and creates a Pair using to

[ephemient]

.chunked() produces a list whose elements are also lists. you can leave them as-is (if lists are acceptable output), or map them to Pair, or use the .chunked() overload that takes a transformation which is semantically equivalent to .chunked() without the transformation followed by a .map() with the transformation

[zain]

transform: (List<T>) -> R

Now I understood transformation in the real sense. It just overload got me confused.
Thank you

[Joffrey]

Again, this solution may work fine, but if this exercise is for you to learn to create a set and pop elements out of it, you might consider writing your own shuffle implementation

[zain]

@Joffrey @ephemient
There are 8 teams and I created fixture of size 4 now I want to create semi from the fixture.
I do random() to the internal list so that I can one element from each fixture and then shuffle and create another semi-final fixture.
What I noticed is the fixture is repeated in the semi-final.
So if T3 v/s T4 is the fixture it is again coming in semi final

val fixtures: List<List<Team>> = teams.shuffled().chunked(2)

assertEquals(fixtures.size, 4)

val semiFinalist = fixtures.map { fixture ->
    fixture.random()
}.shuffled().chunked(2)

assertEquals(semiFinalist.size, 2)

[Joffrey]

The code looks correct at first read though. How did you come to the conclusion that you found an identical team pair in the semi finalists? Do you have a way to reproduce?

[zain]

Because it is random I have to re-run and check and it was returning such values that I found was since it was calling fitures.map it again shuffles and gives random fixtures so it is referring to another fixture for semi-final each time. Now I'm trying by using lazy so that it will only run once

val semiFinalist by lazy {
    randomFixturePairs.map { fixture ->
        fixture.toList().random()
    }.shuffled().chunked(2)
}

[Joffrey]

fixture is already a read-only List, you don't need toList because you don't need to make a copy, especially if you just want to take a random element out of it. (Unless you changed it back to using pairs, in this case, ok).

I don't quite understand what you're trying to do with lazy here. Running the program again will change the random elements anyway, it won't help "remember" state across runs (if that was your goal). If you want to "fix the random", you can use a custom seed.

That said the previous code looked good to me. Are you sure you had run into problems with that code?

[zain]

Yes, the way I run code in the Android environment was re-running each time, that's why the randomness, the previous code works fine. I used lazy to avoid rerunning when I move from one screen to another to remember the state.

[ephemient]

so you're effectively holding it in some singleton outside your UI? that's still problematic, Android is allowed to restart your app between screens. if you want data to persist, you need to persist it - either in local storage or in saved state

[ephemient]

but at this point that's not really anything to do with Kotlin but a general framework usage concern…