"Best fit" problem: Split one array (or list) of strings into 2 arrays (lists)

[BruceG]

Hello all, the problem at hand is as follows: given an array (list) of strings, break up that list into 2 lists having an equal number of items (or as close to equal as possible). Not as easy as it sounds.
The original list in question basically is a list of sentences. If each sentence occupied one list element, there would be no problem: I have a list of 10 lines, divide by 2, and I have my two lists of 5 lines each. But not so fast! The original list my contain sentences that may occupy one, two, or three lines - and when the list is split into two, a rule is that we cannot break up a multi-line sentence.
Here is an example of an initial list (the beginning of each sentence starts with "* "):
(0) * This is a short one.
(1) * Another short one.
(2) * Still another.
(3) * Yet another.
(4) * This is a very long one
(5) spanning a whopping
(6) three lines.
(7) * Back to a short one.
(8) * And another short one.
(9) * Last one here.

So if we keep the original order and split the list at the midpoint, the result is less than desirable. We would get:
LIST 1:
(0) * This is a short one.
(1) * Another short one.
(2) * Still another.
(3) * Yet another.
(4) * This is a very long one
(5) spanning a whopping
(6) three lines.
LIST 2:
(0) * Back to a short one.
(1) * And another short one.
(2) * Last one here.
--- OR ---
LIST 1:
(0) * This is a short one.
(1) * Another short one.
(2) * Still another.
(3) * Yet another.
LIST 2:
(0) * This is a very long one
(1) spanning a whopping
(2) three lines.
(3) * Back to a short one.
(4) * And another short one.
(5) * Last one here.

Although a multi-line sentence is not permitted to broken up (i.e. the long one cannot start at the bottom of LIST 1 and finish at the top of LIST 2), we are permitted to reorder the original list, such that when we split it we get an even number of lines (or as close to even as we can get) per the two lists.
I am looking for an algorithm that figure out how to reorder the original list to accomplish this goal. For example, an algorithm that could determine a reordering of the list as follows:
(0) * Still another.
(1) * Yet another.
(2) * This is a very long one
(3) spanning a whopping
(4) three lines.
(5) * This is a short one.
(6) * Another short one.
(7) * Back to a short one.
(8) * And another short one.
(9) * Last one here.
Which, when split into 2 lists, would give us 5 elements per list:
LIST 1:
(0) * Still another.
(1) * Yet another.
(2) * This is a very long one
(3) spanning a whopping
(4) three lines.
LIST 2:
(0) * This is a short one.
(1) * Another short one.
(2) * Back to a short one.
(3) * And another short one.
(4) * Last one here.

Help is appreciated ...

[.paul.]

Create a new list(of string). Parse the original list, adding to the new list, with every sentence contained in one element. Then it’s easy to split that list into two...

[BruceG]

Thanks for your response, but I can't do what you suggest - the sentences that are multi-line must remain that way, as the application that this is for is to display this data in a 2-column table on a web page. The sentences that are split are split due to a size constraint (i.e. they are sentences that are "wrapped").

[.paul.]

Try this...

Dim l As New List(Of String)(New String() {"* This is a short one.", _
                                                    "* Another short one.", _
                                                    "* Still another.", _
                                                    "* Yet another.", _
                                                    "* This is a very long one", _
                                                    "spanning a whopping", _
                                                    "three lines.", _
                                                    "* Back to a short one.", _
                                                    "* And another short one.", _
                                                    "* Last one here."})
Dim count As Integer = l.Where(Function(sentence) sentence.StartsWith("*")).Count
Dim firstList As List(Of String) = l.Take(count \ 2).ToList
Dim secondList As List(Of String) = l.Skip(count \ 2).ToList

[.paul.]

I'm guessing that still needs more tweaking?

[.paul.]

Will the last line in a long sentence always be terminated with a period?

[.paul.]

Here's a better fit version...

Dim l As New List(Of String)(New String() {"* This is a short one.", _
                                                    "* Another short one.", _
                                                    "* This is a very long one", _
                                                    "spanning a whopping", _
                                                    "three lines.", _
                                                    "* Still another.", _
                                                    "* Yet another.", _
                                                    "* Back to a short one.", _
                                                    "* And another short one.", _
                                                    "* Last one here."})
Dim count As Integer = l.Where(Function(sentence) sentence.StartsWith("*")).Count
Dim f As Integer = count \ 2
Do
    If (l(f).StartsWith("*") And l(f + 1).StartsWith("*")) Then
        Exit Do
    Else
        If l(f).EndsWith(".") Then
            Exit Do
        Else
            If l(f + 1).EndsWith(".") Then
                f += 1
                Exit Do
            Else
                f += 1
            End If
        End If
    End If
    If f = l.Count Then Exit Do
Loop
Dim firstList As List(Of String) = l.Take(f + 1).ToList
Dim secondList As List(Of String) = l.Skip(f + 1).ToList

[BruceG]

The fundamental issue is that the order of the original list will likely need to be changed to accomplish the desired result (my problem is how best to accomplish that reordering). In your code, which relies on the original order, the resulting lists yield 4 elements and 6 elements respectively, where in this case it is possible to get 5 and 5 if the reordering was right.

[.paul.]

Ok. Parse the original list into a list(of String()), where each element is an array of lines. When you have that, it’ll be easy to rearrange by element.length

[ChrisE]

I had a problem a while back to split a Datatable to 3 Datagridviews, not sure about the Split with *


here was my approach with a small sample

Imports System.ComponentModel


Public Class Form1

    Private Sub Button1_Click(sender As System.Object, e As System.EventArgs) Handles Button1.Click
        Dim tbl1 = New DataTable
        tbl1.Columns.Add("ID", GetType(Int32))
        tbl1.Columns.Add("Name", GetType(String))
        tbl1.Rows.Add("1", "ChrisE")
        tbl1.Rows.Add("2", "Tom")
        tbl1.Rows.Add("3", "Sara")
        tbl1.Rows.Add("4", "Smurf")
        tbl1.Rows.Add("5", "Gabi")
        tbl1.Rows.Add("6", "Paul")
        tbl1.Rows.Add("7", "Zoro")
        tbl1.Rows.Add("8", "Ute")
        tbl1.Rows.Add("9", "Peter")
        tbl1.Rows.Add("10", "Annie")
        tbl1.Rows.Add("11", "Helga")
        tbl1.Rows.Add("12", "Dieter")
        tbl1.Rows.Add("13", "Doris")

        Dim tableCount = 3  ' split to 3
        Dim divisor = tbl1.Rows.Count / tableCount
        Dim tables = tbl1.AsEnumerable().
                    Select(Function(r, i) New With {.Row = r, .Index = i}).
                    GroupBy(Function(x) Math.Floor(x.Index / divisor)).
                    Select(Function(g) g.Select(Function(x) x.Row).CopyToDataTable()).ToArray
        'sort by Name
        DataGridView1.DataSource = tables(0)
        DataGridView1.Sort(Me.DataGridView1.Columns("Name"), ListSortDirection.Ascending)
        DataGridView2.DataSource = tables(1)
        DataGridView2.Sort(Me.DataGridView2.Columns("Name"), ListSortDirection.Ascending)
        DataGridView3.DataSource = tables(2)
        DataGridView3.Sort(Me.DataGridView3.Columns("Name"), ListSortDirection.Ascending)
    End Sub

End Class

EDIT:
I think it's just a matter of the Text.Lenght
something like this, and then divide by 2

  Private Sub Button1_Click(sender As System.Object, e As System.EventArgs) Handles Button1.Click
       Dim s As String
        s = ""
        s &= "* This is a short one." & vbNewLine
        s &= "* Another short one." & vbNewLine
        s &= "* Still another." & vbNewLine
        s &= "* This is a very long one" & vbNewLine
        s &= "spanning a whopping" & vbNewLine
        s &= "three lines." & vbNewLine
        s &= "* Back to a short one." & vbNewLine
        s &= "* And another short one." & vbNewLine
        s &= "* Last one here."

        Dim Text() As String = s.Split("*")

        For c As Integer = 1 To Text.Length - 1
            Debug.WriteLine(c & "----------------------")
            Debug.WriteLine(Text(c))
        Next
    End Sub

the debug output

1----------------------
 This is a short one.

2----------------------
 Another short one.

3----------------------
 Still another.

4----------------------
 This is a very long one
spanning a whopping
three lines.

5----------------------
 Back to a short one.

6----------------------
 And another short one.

7----------------------
 Last one here.

[.paul.]

Here's what i was getting at with the list(of string()) idea...

Dim original As New List(Of String)(New String() {"* This is a short one.", _
                                                    "* Another short one.", _
                                                    "* This is a very long one", _
                                                    "spanning a whopping", _
                                                    "three lines.", _
                                                    "* Still another.", _
                                                    "* Yet another.", _
                                                    "* Back to a short one.", _
                                                    "* And another short one.", _
                                                    "* Last one here."})

Dim arrays As New List(Of String())
For x As Integer = 0 To original.Count - 2
    If (original(x).StartsWith("*") And original(x + 1).StartsWith("*")) Then
        arrays.Add(New String() {original(x)})
    Else
        If (original(x).StartsWith("*") And Not original(x + 1).StartsWith("*")) Then
            Dim lines As New List(Of String)
            lines.Add(original(x))
            lines.Add(original(x + 1))
            For y As Integer = x + 2 To original.Count - 1
                If Not original(y).StartsWith("*") Then
                    lines.Add(original(y))
                Else
                    Exit For
                End If
            Next
            arrays.Add(lines.ToArray)
        End If
    End If
Next
If original(original.Count - 1).StartsWith("*") Then arrays.Add(New String() {original(original.Count - 1)})

'try this a few times, or change the contents of the original list above...
arrays = arrays.OrderBy(Function(a) r.NextDouble).ToList

Dim halfCount As Integer = CInt(Math.Ceiling(original.Count / 2))

Dim firstList As New List(Of String)
Dim lengths() As Integer = arrays.ConvertAll(Function(a) a.Length).OrderByDescending(Function(i) i).ToArray

For x As Integer = 0 To lengths.GetUpperBound(0)
    If firstList.Count + lengths(x) <= halfCount Then
        Dim i As Integer = arrays.FindIndex(Function(a) a.Length = lengths(x))
        firstList.AddRange(arrays(i))
        arrays.RemoveAt(i)
    End If
Next

Dim secondList As New List(Of String)

For x As Integer = 0 To arrays.Count - 1
    secondList.AddRange(arrays(x))
Next

[BruceG]

ChrisE - thanks for responding, however you were dealing with all "one-liners" in your example (i.e. you did not have the problem of items that span multiple elements of the list that have to be kept together).

.paul. - thanks very much for your efforts - your latest code example is quite promising, I have tried it on a few scenarios, including my original one, and so far so good! I will continue to test it out.